BFS
-
Q. 1226. 미로 1(D4)코딩테스트/SWEA_Java 2023. 5. 14. 23:27
Q. 1226. 미로 1(D4) 0. 문제 D4 난이도의 문제이지만, 그정도는 아닌 것 같고 단순 그래프 탐색 문제이다. 이동할 수 있는 칸, 이동할 수 없는 칸, 시작 위치, 종료 위치가 주어졌을 때 이동할 수 있는지 계산하는 문제이다. 1. 풀이 전형적인 그래프 탐색 문제이다. BFS를 이용해 풀이했고, 아래와 같은 방식으로 풀었다.자료형은 갈수 없는 벽과 갈 수 있는벽으로 나눠지므로 boolean 타입을 사용했다. 1. 입력을 받으면서 갈 수 있는 벽인지 여부를 저장한다. 또한 시작 위치와 종료 위치도 저장한다.2. 종료 위치에서부터 BFS 탐색을 시작하며, 이전에 방문했던 곳은 표시를 해서 재방문하지 않도록 한다.3. 만약 시작 위치에 도달했을 경우 즉시 루프를 종료하고, 결과를 저장한다. imp..
-
Q. 14940 자바 : 쉬운 최단거리코딩테스트/백준_Java 2023. 4. 22. 23:20
Q. 14940 자바 : 쉬운 최단거리 문제 : boj.kr/14940 실버 1 난이도의 문제이다. 그래프가 주어지고, 시작 정점이 주어질 때 모든 정점의 최단거리를 출력하는 문제이다 주의해야 할 점은 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다는 점 이다 아래와 같은 방법으로 풀었다. 1. 입력은 bool 타입의 2차원 배열로 받았으며, 방문 가느한 위치를 true로 표시했다. (이 때 시작 정점의 위치는 따로 저장해 주었다.) 2. 이후 BFS 순회를 통해 모든 정점을 탐색하며 결과값은 ResArr이라는 2차원 int형 배열에 저장했다. (벽이 아닌 경우 - !Graph[y][x], 방문한 경우 visit[y][x] 에는 방문하지 않았다) 3. 탐색이 끝난 뒤 출력을 위..
-
Q. 4179 자바 : 불!코딩테스트/백준_Java 2023. 4. 21. 18:52
Q. 4179 자바 : 불! 문제 : boj.kr/4179 골드 4 난이도의 문제이고, 탈출 문제와 유사하다 탈출해야 하는 지훈이와 불이 주어지고 불은 점점 확산된다. 이 때 얼마나 빨리 지훈이가 탈출할 수 있는지 계산하는 문제이다. 주의해야 할 점은 불과 지훈이가 같이 있는 경우 탈출할 수 없다. 그래서 BFS 탐색을 사용하기 전에 불을 먼저 queue에 넣어주고 지훈이의 위치를 마지막에 넣었다. 또한 탈출하는 경우는 미로의 가장자리에 있는 경우이고, 탈출 시 이동 횟수가 하나 늘어난다. 아래와 같은 방식으로 풀었다. 1. 입력값은 visit 배열을 이용해서 받았고, 벽(#), 지훈이(J), 화염(F) 모두 방문 체크를 했다. 2. 입력을 받을 때 지훈이와 불의 위치를 모두 저장한 뒤 BFS 탐색 전 ..
-
Q. 2660 자바 : 회장 뽑기코딩테스트/백준_Java 2023. 4. 20. 16:50
Q. 2660 자바 : 회장 뽑기(BFS) 문제 : boj.kr/2660 골드 5 난이도의 문제이다. 간선들이 주어지고, 모든 정점에 방문 가능한 깊이가 가장 적은 사람을 구하는 문제이다. 주의해야 할 점은 출력할 때 회장 후보를 오름차순으로 모두 출력한다는 내용 때문이 있으므로 결과값을 계산한 뒤 정렬이 한번 필요하다. 아래와 같은 방식으로 풀었다. 1. 모든 정점을 계산해야 하므로 모든 정점에 대해 bfs 탐색이 필요하다. 2. 탐색을 할 때 만약 깊이를 줄일 수 있다면 방문한 정점도 다시 탐색한다. (이전 정점을 탐색하지 않도록 주의) 3. 탐색이 끝난 뒤 모든 정점 방문 시 깊이에 대한 값을 계산한다. 이 때 회장 후보일 수 있으므로 결과값과 현재 회장 후보의 값을 비교해 저장한다. 4. 깊이의 ..
-
Q. 18404 자바 : 현명한 나이트코딩테스트/백준_Java 2023. 4. 11. 09:21
Q. 18404 자바 : 현명한 나이트 문제 : boj.kr/18404 실버 1 난이도의 문제이다. 앞의 나이트의 이동 문제와 비슷하다. 나이트의 위치가 주어지고, 잡아야 할 말의 위치가 여러 개 주어진다. 이 때 각각의 말을 나이트가 몇 번 움직여서 말을 잡을수 있는지 출력하는 문제이다. 격자형 그래프 탐색문제에서 상 하 좌 우 순회하는 방식을 응용해탐색하는 범위만 바꾸면 쉽게 풀리는 문제이다. 체스판의 한 변의 길이로 주어지는 N의 최대값이 500이고, 잡아야 할 말의 수 M의 최대값이 1000이다. 따라서 시간복잡도는 아래와 같다. 1. 주어진 말의 수 - O(M) 2. BFS 순회 - O(N ^ 2) 시간복잡도는 약 O(N ^ 2)이고, 최대 2500000번 계산을 하면 문제를 해결할 수 있다. ..
-
Q. 7562 자바 : 나이트의 이동코딩테스트/백준_Java 2023. 4. 10. 09:02
Q. 7562 자바 : 나이트의 이동 문제 : boj.kr/7562 실버 1 난이도의 문제이다. 나이트의 위치가 주어지고, 잡아야 할 말의 위치가 주어진다. 이 때 나이트가 몇 번 움직여서 말을 잡을수 있는지 출력하는 문제이다. 격자형 그래프 탐색문제에서 상 하 좌 우 순회하는 방식을 응용해 탐색하는 범위만 바꾸면 쉽게 풀리는 문제이다. 체스판의 한 변의 길이로 주어지는 I의 최대값이 300이므로 시간복잡도는 1. BFS 순회 - O(I ^ 2) 한번으로 최대 90000번 계산을 하면 문제를 해결할 수 있다. 따라서 시간초과는 걱정하지 않아도 된다. 또한 자료형 역시 int 범위 내에서 모두 해결할 수 있다. 풀이는 아래와 같다. import java.io.*; import java.util.*; pub..
-
Q. 3055 자바 : 탈출코딩테스트/백준_Java 2023. 4. 9. 13:27
Q. 3055 자바 : 탈출 문제 : boj.kr/3055 골드 4 난이도의 문제이다. 격자형 그래프가 주어지고, 비어있는 곳은 '.', 물이 차있는 지역은 '*', 돌은 'X', 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 주어질 때 S가 D로 갈 수 있는 최단경로를 계산하는 문제이다. 주의해야 할 점은 물이 차있는 지역인 *는 비어있는 곳 '.'로 확산되고, 물이 차있는 지역은 고슴도치가 갈 수 없다는 점 이다. 어떻게 풀지 고민을 해봤더니, 먼저 물이 차있는 곳에 대해 BFS를 하고 이후에 고슴도치가 BFS를 하면 풀 수 있을 것 같아 이렇게 풀었다. 1. 물이 차있는 곳을 큐에 넣는다. 2. 고슴도치의 위치는 저장했다가, 물이 차있는 곳이 모두 큐에 들어가면 이후에 큐에 넣는다. 3. 탐색을..
-
Q. 1697 자바 : 숨바꼭질코딩테스트/백준_Java 2023. 4. 8. 13:16
Q. 1697 자바 : 숨바꼭질 문제 : boj.kr/1697 실버 1 난이도의 문제이다. 두 점 N, K가 주어지고, N이 이동할 수 있는 방식은 총 3개이며 각각 1초가 소요된다면(N + 1, N - 1, N * 2)N이 K로 갈 수 있는 가장 빠른 시간을 구하는 문제이다. 만약 그래프 탐색 관련 문제를 풀고 있지 않았다면처음 이 문제를 봤을 때 그래프 탐색 문제라고 생각하지 못했을 것 같다.고민해보니 세가지 이동방식에 대한 BFS를 이용하면 풀 수 있을 것 같아 이 방식을 이용해서 풀었다. 1. 정점 N에서 이동 가능한 세 가지 방식에 따른 좌표를 큐에 넣는다.2. 만약 방문했다면 재방문하지 않는다.(가장 먼저 방문한 경우가 가장 빠른 경우이므로 재방문했다면 더 빨라질 수는 없다.) 시간복잡도를 계..