반응형 알고리즘/너비 우선 탐색(bfs)24 백준 2665번 : 미로만들기 java 이 문제는 미로의 구조를 입력받은 뒤 방을 최대한 적게 바꾸고 끝 점에 도달할 때 몇 개의 방을 바꾸어야 하는지에 대한 문제입니다. 이 문제를 풀기 위해서는 큐에 정점의 좌표와 그 좌표에 도달할 때 몇 개의 방을 바꾸었는지를 저장한 후 방을 바꾼 개수를 기준으로 정점들을 오름차순으로 정렬해야 합니다. 이를 위해서 우선순위 큐를 사용하였고 큐에서 꺼낸 정점들은 bfs를 이용하여 주변의 노드들을 탐색해주었습니다. import java.io.*; import java.util.*; public class Main { static int N; static int[][] map; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; public st.. 2022. 7. 5. 백준 2573번 : 빙산 java 이 문제는 너비 우선 탐색을 여러 번 활용하여 문제에서 주어진 조건에 맞게 프로그램을 만드는 문제입니다. 저는 이 문제를 풀기 위해서 빙산이 이어져 있나를 확인하기 위해서 bfs를 먼저 한번 사용하였고 빙산이 1개로 이어져 있을 경우 빙산을 녹여야 하기 때문에 이때 bfs를 한번 더 사용하였습니다. 빙산이 2개 이상이 되었을 경우에는 그렇게 되기 까지의 시간을 출력하여 주었고 빙산이 0개가 되었을 경우에는 빙산이 다 녹을 때까지 분리되지 않았음을 의미하므로 0을 출력해줍니다. import java.io.*; import java.util.*; public class Main { static int N, M; static int[][] map; static boolean[][] visited; static.. 2022. 7. 4. 백준 2583번 : 영역 구하기 java 이 문제는 사각형의 좌표를 입력받아서 그 안에 속한 좌표들을 전부 1로 초기화한 다음 사각형에 속하지 않은 부분들이 몇 개가 있는 지를 확인하고 그 영역들의 넓이를 오름 차순으로 정렬하는 문제입니다. 위의 그림과 같은 상황일 때는 3개의 공간으로 사각형에 의해서 나누어지고 각 영역의 넓이가 1, 7, 13이기 때문에 이를 오름차순으로 정렬하여 출력합니다. 저는 이를 사각형의 좌표를 입력받아서 그 영역에 속한 부분들을 1로 초기화한 다음 나머지 칸들을 순회하면서 0인 부분들을 1로 바꾸며 영역의 개수와 그 넓이를 확인하였습니다. import java.io.*; import java.util.*; public class Main { static int M, N, cnt = 0; static int[][] m.. 2022. 7. 3. 백준 5567번 : 결혼식 java 이 문제는 친구관계를 입력받아서 결혼식에 올 사람들의 수를 구하는 문제입니다. 상근이의 학번은 1이고 자신의 친구들과 친구의 친구들을 결혼식에 부르려고 합니다. 따라서 입력들을 저장한 후 친구들과 친구의 친구들까지의 수를 세서 출력하면 됩니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); List l = new ArrayList(); for.. 2022. 7. 2. 백준 18405번 : 경쟁적 전염 java 이 문제는 우선순위 큐를 이용하여 입력을 받아준 후 bfs를 이용하면 되는 문제입니다. 이 문제에서는 N x N 크기의 시험관에서 K종류의 바이러스가 존재한다고 합니다. 그리고 이 바이러스는 숫자가 낮은 바이러스부터 차례대로 주변으로 한 칸씩 증식합니다. 이때 바이러스가 증식하는 순서를 정렬하기 위해서 PriorityQueue를 사용해줍니다. 그리고 각 초마다 증식하기 때문에 각 초마다 주변으로 1칸씩 우선순위 큐에 들어있는 순서대로 증식하게 만듭니다. 그리고 (3, 2) 칸에 바이러스가 존재한다면 바로 종료하도록 만들었습니다. 바로 코드를 보여드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int N; static.. 2022. 7. 1. 백준 1261번 : 알고스팟 java 이 문제는 벽을 최대한 적게 부수면서 (1, 1)에서 (N, M)까지 갈 때 부순 벽의 개수를 출력하는 문제입니다. 이 문제를 언뜻 보았을 때 dfs를 이용해서 벽을 부수면서 탐색해야 할 것처럼 보입니다. 하지만 이 문제는 끝까지 갔을 때 부순 벽의 개수가 최소가 되어야합니다. 따라서 bfs를 이용해서 주변을 탐색하며 끝까지 가장 벽을 적게 부수고 가는 경우의 수를 찾아야 합니다. 이를 위해서 PriorityQueue에 각각의 노드의 정보와 벽을 몇 개를 부수었는지에 대한 정보를 넣고 벽을 부신 개수를 오름차순으로 정렬하여 벽을 가장 적게 부수고 끝 점까지 가는 방법을 찾아야 합니다. 이에 대한 코드를 보여드리도록 하겠습니다. import java.io.*; import java.util.*; publi.. 2022. 6. 27. 백준 16236번 : 아기 상어 java 이 문제는 bfs를 이용해서 아기 상어가 엄마 상어에게 도움을 받지 않고 얼마나 물고기를 먹으러 이동할 수 있는지를 구하는 문제입니다. 이 문제의 초기 조건은 아래와 같습니다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 여기서 아기 상어가 상하좌우로 1칸씩 이동할 수 있다는 것에서 bfs를 사용할 수 있을 것이라는 생각을 했습니다.. 2022. 6. 25. 백준 2589번 : 보물섬 java 이 문제는 bfs를 이용하여 섬 안에서 가장 먼 거리에 보물을 묻을 때 보물 간의 거리를 구하는 문제입니다. 이 문제를 풀 때는 브루트포스 알고리즘을 사용해야 합니다. 지도의 각 칸을 탐색하면서 탐색한 칸이 땅일 때 연결된 땅들을 전부 탐색하면서 가장 거리가 먼 땅을 찾습니다. 코드를 보면서 조금 더 설명드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int row, col; static char[][] map; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; static int max = 0; public static void main(Strin.. 2022. 6. 24. 이전 1 2 3 다음 반응형
