반응형 알고리즘/너비 우선 탐색(bfs)24 백준 2468번 : 안전 영역 java 이 문제는 배열의 각 칸을 순회하면서 bfs를 이용하여 연결된 안전 영역들을 탐색하는 문제입니다. 연결된 안전 영역들의 개수를 파악하는 문제입니다. 코드를 보면서 추가로 설명드리겠습니다. import java.io.*; import java.util.*; public class Main { static int N, safe = 0; static int minHeight = Integer.MAX_VALUE; static int maxHeight = Integer.MIN_VALUE; static int[][] map; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; public static void main(String[] args) th.. 2022. 6. 23. 백준 2636번 : 치즈 java 이 문제는 너비 우선 탐색을 이용하여 다음에 없어질 치즈들을 큐에 저장한 후에 그다음 시간에 모든 치즈들이 사라지면 순회를 종료하는 알고리즘입니다. 이 문제를 풀 때 조심하셔야 하는 점은 밖의 공기와 접한 치즈들만 녹아서 없어진다는 것입니다. 위의 그림에서 없어지는 부분들을 확인해 보시면 안의 공기와 맞닿은 부분들은 녹지 않는데 밖의 공기와 맞닿은 부분들만 녹습니다. 따라서 우리는 밖의 공기와 접해 있는 치즈의 부분들만 큐에 넣은 후 제거해야 한다느 것을 알 수 있습니다. 또한 이 문제를 풀 때 공기와 맞닿은 치즈 부분들을 바로 큐에서 제거하면 안됩니다. 다음 차례에서 모든 치즈들이 사라진다면 남아 있는 치즈들의 개수를 세야 하는데 치즈들을 바로 없애면 이를 할 수 없기 때문입니다. 따라서 저는 이 문제.. 2022. 6. 20. 백준 11725번 : 트리의 부모 찾기 java 이 문제는 루트 노드가 정해져 있으니 루트 노드로부터 시작하여 간선들을 bfs를 이용하여 만나는 노드들을 조건에 맞게탐색하는 문제입니다. 저는 이 문제를 해결하기 위해 N개의 ArrayList를 List안에 넣어서 각각의 자리를 노드의 시작점으로 사용하였습니다. 그리고 1번 노드가 루트 노드이니 루트 노드에서 시작하여 연결된 간선들에 부모 노드를 입력하면서 진행하였습니다. 코드를 보여드리도록 하겠습니다. import java.util.*; import java.io.*; public class Main { static List l; static int[] answer; public static void main(String[] args) throws IOException{ BufferedReader br.. 2022. 6. 10. 백준 12851번 : 숨바꼭질 2 java 이 문제는 가장 빠른 시간으로 동생을 찾을 수 있는 시간과 이렇게 찾는 방법이 몇 가지인지를 찾는 문제입니다. 이 문제를 풀 때 유의하셔야 하는 점은 중복을 허용해주어야 한다는 것입니다. 5에서 17로 갈 때는 아래와 같이 중복이 없을 수도 있습니다. 하지만 1에서 4로 갈 때를 살펴보겠습니다. 다음과 같이 같은 칸으로 같이 시간이 걸려서 갈 때도 있기 때문에 중복을 허용해 주어야 합니다. 따라서 우리는 중복을 허용해주면서 더 이상 queue에 값을 넣지 않는 상황을 설정해주어야 합니다. 중복을 허용해 주지 않는 상황들을 아래에 나열하도록 하겠습니다. 1. 도착 지점의 시간값이 지금 노드의 시간 값보다 작을 때 bfs를 사용하여 위 문제를 풀 때 모든 간선의 가중치가 같기 때문에 다음 노드로 나아갈 때 .. 2022. 6. 4. 백준 13549번 : 숨바꼭질 3 java 이 문에는 *2 +1 -1로 이동하면서 bfs에 노드들을 삽입하면서 문제를 해결하면 됩니다. 이때 유의하셔야 하는 점은 *로 가는 연산을 먼저 해야 연산 횟수를 줄일 수 있기 때문에 이 연산을 먼저 해야 한다는 것입니다. 또한 같은 자리에 나중에 도착하게 되더라도 *2할 때 걸리는 시간이 0이기 때문에 더 적은 시간으로 올 수도 있습니다. 따라서 min 변수를 Math.min으로 초기화하면서 저장해야 합니다. 이를 그림으로 설명드리겠습니다. 위의 그림과 같이 1 2 3 4이라는 수가 있습니다. 이를 +1연산으로만 채워보겠습니다. 그럼 각 자리까지 가는 시간은 위의 그림과 같습니다. 이제 *2연산을 더해보도록 하겠습니다. 1에서 시간한다고 할 때 2까지는 순간이동이니 시간이 들지 않고 4도 마찬가지입니다... 2022. 6. 3. 백준 16953번 : A → B java 이 문제는 bfs를 이용하여 A가 조건에 맞게 바뀔 때 B로 가장 적은 연산으로 바뀌는 연산의 수를 구하는 문제입니다. 바로 코드를 보여드리겠습니다. import java.util.*; import java.io.*; public class Main{ static int B; static boolean get; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int A = Integer.parseInt(st.nextT.. 2022. 6. 1. 백준 15686번 : 치킨 배달 java 이 문제는 정해진 개수의 치킨집에서 가장 짧은 거리를 이동하여 지도에 있는 모든 집들에 배달을 마무리할 수 있게 하는 문제입니다. 이 문제는 소스 코드를 보면서 설명해드리도록 하겠습니다. import java.util.*; import java.io.*; public class Main{ static int N, M; static int[][] map; static LinkedList chicken = new LinkedList(); static int min = Integer.MAX_VALUE; static int[] drow = {0, 0, 1, -1}; static int[] dcol = {1, -1, 0, 0}; public static void main(String[] args) throws I.. 2022. 5. 28. 백준 14502번 : 연구소 java 이 문제는 dfs와 bfs를 이용하여 푸는 브루트포스 문제입니다. 소스 코드를 보면서 설명하도록 하겠습니다. import java.util.*; import java.io.*; public class Main{ static int N, M; static int[][] map; static int max = Integer.MIN_VALUE; static int[] drow = {0, 0, 1, -1}; static int[] dcol = {1, -1, 0, 0}; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri.. 2022. 5. 28. 이전 1 2 3 다음 반응형
