백준 2665번 : 미로만들기
이번 문제는 n*n 크기의 바둑판 모양의 그래프에서 0은 검은 방, 1은 흰 방일 때 1은 통과가 가능하고 0은 통과가 불가능하다.
시작 위치를 (0, 0), 종료 위치를 (n - 1, n - 1)이라고 했을 때, 시작 위치에서 종료 위치까지 도달하는데 검은 방을 흰방으로 몇 번 바꾸어야 최단 거리로 도달 가능한지를 리턴하는 문제이다.
단, 검은 방을 흰 방으로 하나도 바꾸지 않고서 도달이 가능한 경우는 0이 리턴되어야한다.
이 문제를 풀기 위해 가장 먼저 change 라는 각 칸까지 도달하기 위해 변경해야하는 최소 횟수를 저장하는 배열을 선언했다.
이 배열은 아래와 같이 기본 그래프 배열인 arr이 초기화되어 값이 할당 될 때 동시에 초기화하고 각 값을 최댓값으로 할당한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Main {
static int n;
static int[][] arr;
static int[][] change; // 각 칸까지 도달하기 위해 변경해야 하는 최소 횟수를 저장
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1}; // 상, 우, 하, 좌 이동을 위한 배열
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine()); // 미로의 크기
arr = new int[n][n]; // 미로를 나타내는 배열
change = new int[n][n]; // 변경 횟수를 저장할 배열
for (int i = 0; i < n; i++) {
String line = br.readLine();
for (int j = 0; j < n; j++) {
arr[i][j] = line.charAt(j) - '0';
change[i][j] = Integer.MAX_VALUE; // 최대값으로 초기화
}
}
System.out.println(bfs());
}
다음은 bfs 탐색인데, 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘인 다익스트라와 비슷하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static int bfs() {
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
pq.offer(new int[]{0, 0, 0}); // 시작점 (0,0)과 변경 횟수 0을 우선순위 큐에 추가
change[0][0] = 0; // 시작점의 변경 횟수는 0
while (!pq.isEmpty()) { // 우선순위 큐가 비어 있지 않는 동안 반복
int[] cur = pq.poll(); // 우선순위 큐에서 변경 횟수가 가장 작은 칸을 꺼냄
int x = cur[0], y = cur[1], cnt = cur[2]; // 현재 칸의 좌표와 변경 횟수
if (x == n - 1 && y == n - 1) { // 도착점에 도달했으면 반복 종료
return cnt; // 변경 횟수 반환
}
for (int i = 0; i < 4; i++) { // 상하좌우 이동을 위한 반복문
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) { // 미로 안에 있는지 확인
int nextCnt = cnt + (arr[nx][ny] == 0 ? 1 : 0); // 다음 칸이 검은 방이면 변경 횟수 1 증가
if (change[nx][ny] > nextCnt) { // 기존보다 더 적은 변경 횟수로 갈 수 있다면
change[nx][ny] = nextCnt; // 변경 횟수 업데이트
pq.offer(new int[]{nx, ny, nextCnt}); // 새로운 변경 횟수로 우선순위 큐에 추가
}
}
}
}
return 0;
}
다익스트라는 가중치가 있는 그래프에서 작동하는데, 각 정점까지 도달하는 데 필요한 최소 비용을 계산한다.
다시 말해 가중치의 ‘합’을 계산한다.
유사한 점은 다음과 같다.
- 최소 비용 우선 : 현재 bfs에서 우선순위 큐를 활용해 변경 횟수가 가장 적은 칸을 우선 탐색한다.
- 그리디 방식 : 다익스트라는 그리디의 일종이다. 다시 말해, 각 단계에서 최적의 선택을 한다. 위의 bfs 탐색에서도 각 단계의 최소 변경 횟수를 선택하고 있다.
- 최적 상태 갱신 : change 배열을 사용하여 각 칸까지 도달하기 위해 필요한 최소 변경 횟수를 지속 갱신한다.
- 가중치 업데이트 : 다익스트라는 새로운 노드를 방문할 때마다 가중치를 업데이트하는데, 위 bfs에서 도 마찬가지로 검은 방을 만났을 때 변경 횟수를 증가시키고 우선 순위 큐에 넣어 최소 변경 횟수를 찾는다.
이 문제에 사용된 알고리즘은 다익스트라의 변형이라고 할 수 있을 정도로 유사한 점이 많다.
다만, 구현을 간단히 하기 위해, 또한, 가중치가 1과 0만 존재하기 때문에 다익스트라 대신 BFS 탐색을 활용했다.
더 복잡한 그래프인 경우는 다익스트라를 활용해야할 것이다.
다시 bfs로 돌아와,
위 알고리즘에 대한 설명은 다음과 같다.
- 우선순위큐를 활용하여 변경 횟수에 따라 우선 순위를 정해 방을 탐색한다. 즉, 변경 횟수가 적은 방을 먼저 탐색한다.
- 큐가 빌 때까지, 탐색을 반복한다.
- 가장 먼저 현재 위치가 목적지 인지 확인한다. 목적지에 도달했다면, 그 위치까지 도달하기 위한 변경한 방의 수를 반환하고 알고리즘을 종료한다.
- 상하좌우를 이동하며 다음을 수행한다.
- 다음 위치가 흰 방인 경우, 현재까지의 변경 횟수를 유지한다.
- 다음 위치가 검은 방인 경우, 현재까지 변경 횟수에 1을 더한다.
- 다음 위치까지 도달하기 위한 기존의 최소 변경 횟수(change[nx][ny])보다 더 적은 변경 횟수로 도달할 수 있다면, 최소 변경 횟수를 업데이트하고 큐에 새 위치를 삽입한다.
- 마지막으로 탐색이 끝나면 목적지까지 도달하기 위한 최소 변경 횟수가 change 배열에 저장된다.
여기서 change 배열은 각 칸까지 도달하기 위해 필요한 최소 변경 횟수를 저장하기 위해 사용되는데, 이 정보는 탐색 과정에서 각 단계에서 해당 칸에 대한 최소 변경 횟수가 이미 발견된 변경 횟수보다 적을 때만 해당 칸을 큐에 다시 추가하는데에 사용된다.
1
2
3
4
5
if (change[nx][ny] > nextCnt) {
change[nx][ny] = nextCnt;
pq.offer(new int[]{nx, ny, nextCnt});
}
이 코드에서 다음 위치로 이동할 때 이전에 발견된 최소 변경 횟수보다 새로 계싼된 변경 횟수가 적을 경우에만 change 배열을 갱신하고 새로운 위치를 우선 순위 큐에 추가한다.
이 부분에서 다익스트라 알고리즘의 최소 비용 갱신 방식과 유사하다고 할 수 있다.
이 change 배열은 각 위치까지의 최소 변경 횟수를 효과적으로 추적하고, 우선순위 큐를 활용하여 불필요한 탐색을 줄이기 위해 필요하다.
전체 소스 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n;
static int[][] arr;
static int[][] change;
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
change = new int[n][n];
for (int i = 0; i < n; i++) {
String line = br.readLine();
for (int j = 0; j < n; j++) {
arr[i][j] = line.charAt(j) - '0';
change[i][j] = Integer.MAX_VALUE;
}
}
System.out.println(bfs());
}
public static int bfs() {
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
pq.offer(new int[]{0, 0, 0});
change[0][0] = 0;
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int x = cur[0], y = cur[1], cnt = cur[2];
if (x == n - 1 && y == n - 1) {
return cnt;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
int nextCnt = cnt + (arr[nx][ny] == 0 ? 1 : 0); // 검은 방을 만나면 cnt를 1 증가
pq.offer(new int[]{nx, ny, nextCnt});
}
}
}
return 0;
}
}
난이도가 골드만 넘어가면 헐떡댄다…
이전에 풀었던 벽 부수고 이동하기 문제와 유사한가 싶었지만 전혀 다른 문제였다.
검은 방, 흰 방으로 나뉘고 변경하는 것을 어떻게 해야할지 엄청 헤맸다.
찾아보니 가중치를 기반으로 탐색하는 힌트가 있었어서 겨우 도움 받아 풀었다.