백준 2206번 : 벽 부수고 이동하기
이번 문제는 n*m의 행렬이 있을 때, 이동할 수 있는 칸은 0, 벽이 있는 곳은 1로 표현된다.
이 행렬을 바탕으로 최대 한번만 벽을 부수고 지나갈 수 있다.
이때, 최단 거리로 이동한 횟수를 리턴해야한다.
솔직히 문제 자체는 어려울 것 없이 이해는 되지만 구현이 힘들다.
우선 이 문제를 풀기 위해 최단 거리이기 때문에 당연히 BFS를 사용했으며,
추가한 점은 목적지까지 벽을 부순 경우, 부수지 않은 경우 두 가지 중 최소 이동횟수를 뽑아내기 위해서
기본 맵인 이차원 배열 arr은 그대로 두고 삼차원 배열인 dst를 하나 초기화하여 해당 배열에 이동을 표현했다.
가장 먼저 앞서 설명했듯이 dst를 포함한 멤버 변수를 선언했다.
1
2
3
4
5
6
7
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int[][] arr;
static int[][][] dst;
static boolean[][][] visited;
static int n,m;
dst는 설명했고, 이외의 변수들은 큰 설명이 필요없을 것이다.
이미 자주 보았던 것들이기 때문에
다음으로는 행렬 가공과 각 배열 초기화인데,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args) throws java.io.IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
dst = new int[n][m][2];
visited = new boolean[n][m][2];
for (int i = 0; i < n; i++) {
String r = br.readLine();
for (int j = 0; j < m; j++) {
arr[i][j] = Integer.parseInt(String.valueOf(r.charAt(j)));
}
}
bfs();
arr, 행렬을 초기화하고 값을 삽입해 그래프를 만드는 것은 이전에 풀었던 문제들과 동일하다.
특히 dst와 visited는 3차원 배열로 초기화했는데,
이는, 벽을 부수고 이동한 경우와 벽을 부수지 않고 이동한 경우를 구분하기 위함이다.
3차원 중 첫 번째는 부수지 않고 이동한 경우, 두 번째는 벽을 부수고 이동한 경우를 나타낸다.
다음으로는 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 void bfs() {
Queue<int[]> q = new LinkedList<>();
visited[0][0][0] = true;
dst[0][0][0] = 1;
q.offer(new int[]{0,0,0});
while(!q.isEmpty()) {
int[] cur = q.poll();
int wall = cur[2];
for (int i = 0; i < 4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (arr[nx][ny] == 0 && !visited[nx][ny][wall]) {
q.offer(new int[]{nx, ny, wall});
visited[nx][ny][wall] = true;
dst[nx][ny][wall] = dst[cur[0]][cur[1]][wall] + 1;
}
if (arr[nx][ny] == 1 && wall == 0 && !visited[nx][ny][wall + 1]) {
q.offer(new int[]{nx, ny, wall + 1});
visited[nx][ny][wall + 1] = true;
dst[nx][ny][wall + 1] = dst[cur[0]][cur[1]][wall] + 1;
}
}
}
}
}
처음에는 3차원 배열로 표현된 dst와 visited 때문에 더 헷갈려서 bfs를 벽을 부수는 행위 없는 일반 탐색으로 구현했었다.
그 이후 다시 벽을 부순 경우, 부수지 않은 경우로 천천히 나누어 구현했다.
큐를 선언해 시작 위치인 (0,0)을 방문했다는 표시를 하고, 이동 거리를 1로 설정한다.
그리고 시작 위치와 벽을 부수지 않았다는 정보를 가진 배열을 큐에 삽입한다. (2번 째 인덱스)
큐가 빌 때까지 탐색을 작업을 시작하는데,
상하좌우 이동하며 체크하는 방식은 기존과 동일하나, 다음과 같은 조건이 분기되었다.
- 이동하려는 칸이 벽이 아니고, 아직 방문하지 않았다면 이동한다. 이동하려는 칸을 방문 체크해주고 이동거리를 갱신한다. 또한, 이동한 위치와 벽을 부수지 않았다는 정보를 가진 배열을 큐에 넣는다.
- 이동하려는 칸이 벽이고, 아직 벽을 부수지 않았다면 벽을 부수고 이동한다. 이동하려는 칸을 방문했다는 표시를 하고 이동 거리를 갱신한다. 또한, 이동한 위치와 벽을 부순다는 정보를 가진 배열을 큐에 넣는다.
이 두 가지의 경우가 3차원에 0,1 인덱스로 각각 들어가고 이 작업을 반복하여 0 = 벽을 부수지 않고 최단거리 와 1 = 벽을 부수고 최단거리를 저장한다.
이후 bfs가 종료되면 메인 함수로 돌아와 다음과 같은 조건을 분기하여 이동 거리를 출력한다.
1
2
3
4
5
6
7
8
9
if (dst[n - 1][m - 1][0] == 0 && dst[n - 1][m - 1][1] == 0) {
System.out.println(-1);
} else if (dst[n - 1][m - 1][0] == 0) {
System.out.println(dst[n - 1][m - 1][1]);
} else if (dst[n - 1][m - 1][1] == 0) {
System.out.println(dst[n - 1][m - 1][0]);
} else {
System.out.println(Math.min(dst[n - 1][m - 1][0],dst[n - 1][m - 1][1]));
}
첫 번째 분기는 벽을 부수든 부수지 않든 목적지에 도달할 수 없는 경우이다. 이 경우 -1을 리턴한다.
두 번째 분기는 벽을 부수어야 목적지에 도달할 수 있는 경우이다. 이 경우는 벽을 부수고 이동한 거리를 리턴한다.
세 번째 분기는 벽을 부수지 않아야 목적지에 도달할 수 있는 경우이다. 이 경우는 벽을 부수지 않고 이동한 거리를 리턴한다.
마지막 분기는 두, 세 번째가 모두 가능한 경우이므로 둘 중에 최단 거리를 리턴한다.
이렇게 함으로써 최대 1회 벽을 부술 수 있는 경우의 최단 거리를 리턴하게 된다.
전체 소스 코드는 다음과 같다.
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int[][] arr;
static int[][][] dst;
static boolean[][][] visited;
static int n,m;
public static void main(String[] args) throws java.io.IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
dst = new int[n][m][2];
visited = new boolean[n][m][2];
for (int i = 0; i < n; i++) {
String r = br.readLine();
for (int j = 0; j < m; j++) {
arr[i][j] = Integer.parseInt(String.valueOf(r.charAt(j)));
}
}
bfs();
if (dst[n - 1][m - 1][0] == 0 && dst[n - 1][m - 1][1] == 0) {
System.out.println(-1);
} else if (dst[n - 1][m - 1][0] == 0) {
System.out.println(dst[n - 1][m - 1][1]);
} else if (dst[n - 1][m - 1][1] == 0) {
System.out.println(dst[n - 1][m - 1][0]);
} else {
System.out.println(Math.min(dst[n - 1][m - 1][0],dst[n - 1][m - 1][1]));
}
}
public static void bfs() {
Queue<int[]> q = new LinkedList<>();
visited[0][0][0] = true;
dst[0][0][0] = 1;
q.offer(new int[]{0,0,0});
while(!q.isEmpty()) {
int[] cur = q.poll();
int wall = cur[2];
for (int i = 0; i < 4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (arr[nx][ny] == 0 && !visited[nx][ny][wall]) {
q.offer(new int[]{nx, ny, wall});
visited[nx][ny][wall] = true;
dst[nx][ny][wall] = dst[cur[0]][cur[1]][wall] + 1;
}
if (arr[nx][ny] == 1 && wall == 0 && !visited[nx][ny][wall + 1]) {
q.offer(new int[]{nx, ny, wall + 1});
visited[nx][ny][wall + 1] = true;
dst[nx][ny][wall + 1] = dst[cur[0]][cur[1]][wall] + 1;
}
}
}
}
}
}
문제가 너무 어려웠다.
벽을 부수고 이동하는 것 자체를 생각해본 적도 없다.
그런데 뭔가 실제로 있을 법한 일이라 두렵다.
내가 푼 방식 이외에도 좋은 방법들이 많다.
솔직히 이번 풀이는 부분적으로 copilot의 도움을 받았다.
기본적인, 즉, 벽을 부수는 행위 없는 bfs는 금방 작성했는데 이걸 어떻게 벽을 부순 경우와 아닌 경우를 나누어야 할지 감이 안잡혔다.
처음에는 visited를 3차원 배열로 만들어 해당 두 가지 경우를 나타냈는데 dst 배열은 선언하지 못했다.
단순히 arr 안에서 전부 해결하려고 했는데, 탐색 문제에서 무언가 조건이 분기되어서 여러 경우가 나올 수 있다면 또다른 배열을 만들어 거기에 표현하는 것이 더욱 낫다는 것을 깨달았다.
어찌됐든 아주 어려웠는데 정답률도 낮고 해서 난이도를 봤더니 골드3이더라.
앞으로는 골드3도 수월하게 풀 수 있으면 좋겠다.