본문 바로가기

BFS4

[자바] 백준 1697 - 숨바꼭질 난 BFS로 풀었는데, 사실 DFS가 더 빠를 수 밖에 없을 것 같다. 그리고 넘 쉽게 풀어서 분명 난이도가 높아지는 시리즈 문제들이 있을 거라고 생각했는데, 진짜 있다. 얼핏 봤을 때에는 숨바꼭질 4까지는 N, K 범위도 똑같고 문제도 거의 유사한 것 같은데 난이도가 차이나서 뭐지 싶다. 테스트 데이터 차이인가? /* 2020.12.12(토)*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] arg.. 2020. 12. 12.

[자바] 백준 1012 - 유기농 배추 문제는 BFS로 간단히 풀리는데, N과 M의 방향 때문에 헷갈린다. 나는 배열의 사이즈를 나타낼 때 array[n][m] 이렇게 많이 사용하는데, 따지고 보면 세로의 길이를 가로의 길이보다 먼저 나타내는 거다. 근데 문제 입력에서는 (X,Y) 순으로 주어진다. 즉, 좌표 평면을 생각할 때 많이 사용하는 방식으로 가로 위치를 세로 위치보다 먼저 알려주는 것! 별 거 아닐 수도 있는데, 코드짤 때 Y를 앞에 두고 생각할라니까 뭔가 낯설어서 헷갈렸다. N이 M보다 먼저 오는 건 하나도 안 헷갈리는데! /* 2020.12.06(일)*/ import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; impor.. 2020. 12. 6.

[자바] 백준 2667 - 단지번호붙이기 풀때마다 새롭다. 신기하다. 네 방향을 왔다 갔다 할 수 있도록 2차원 int배열을 만들어서 for문으로 하나씩 que에 담아주는 부분이 항상 헷갈린다. int[][] dir = { {0,1}, {0,-1}, {1,0}, {-1,0} }; BFS에서는 que 안에서 if문의 조건을 제대로 세우는 단계가 제일 까다롭게 느껴진다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.Queue; public class Main2667_단지번호붙이기 { static.. 2020. 12. 6.

[자바] 백준 2606 - 바이러스 어려운 문제도 이렇게 쉽게 풀렸으면 좋겠다 하하하하하 ArrayList 배열을 만들어서 BFS로 풀었다. Queue에다가 1이랑 이어진 컴퓨터들 번호 넣고, infected 여부 체크해서 infected=false인 컴퓨터들만 다시 큐에다가 집어 넣어줬다. 이미 감염 확인된 컴퓨터라면 감염을 확인한 시점에 연결된 컴퓨터들을 다 큐에다가 넣어줬을 테니까! N의 범위가 작아서 인접 리스트 대신에 N+1 x N+1 행렬을 만들어서 체크했어도 됐을 것 같다. 음 예를 들어, network[A][B] = 1 = network[B]=[A] 이런 식으로? import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList.. 2020. 12. 5.

이전 1 다음

티스토리툴바