백준 벽 부수고 이동하기 [2206번]
문제
입력과 출력 양식
예제 입력과 출력
예제 1
입력
1
2
3
4
5
6
7
6 4
0100
1110
1000
0000
0111
0000
출력
1
15
예제 2
입력
1
2
3
4
5
4 4
0111
1111
1111
1110
출력
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
75
76
77
78
79
import java.util.*;
import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] rowAndColumn = bf.readLine().split(" ");
int row = Integer.parseInt(rowAndColumn[0]);
int column = Integer.parseInt(rowAndColumn[1]);
int[][] grid = new int[row][column]; // 격자판을 저장할 배열
//일반적인 방문여부 변수와는 다르게 벽을 부쉈는지(1) 안 부쉈는지(0)를 추가하여 3차원 배열로선언
boolean[][][] visited = new boolean[row][column][2];
// 격자판 데이터 입력 받기
for (int r = 0; r < row; r++) {
String line = bf.readLine();
for (int c = 0; c < column; c++) {
grid[r][c] = Character.getNumericValue(line.charAt(c));
}
}
int result = bfs(row, column, grid, visited);
System.out.println(result);
}
static int[][] direction = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
public static int bfs(int row, int column, int map[][], boolean[][][] visited) {
Queue<int[]> queue = new LinkedList<>();
// 배열의 각 요소의 의미는 x좌표, y좌표 ,이동 거리, 벽을 부수고 왔는지 확인
// 부쉈으면 1, 안 부쉈다면 0이다. 처음 시작 좌표 0,0 에서는 아직 안부쉈으므로 0으로 선언했다.
queue.add(new int[]{0,0,1,0});
visited[0][0][0] = true; //x,y,부순경로인지아닌지 (0이 안부순거, 1이 부순거)
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
int distance = current[2];
int isBroken=current[3];
if (x == row - 1 && y == column - 1) {
return distance;
}
for (int[] dir : direction) {
int newX = x + dir[0];
int newY = y + dir[1];
//일단 2차원 격자판안에서 좌표들이 존재하는지 확인
if(!(newX>=0 && newX<row && newY>=0 && newY<column)){continue;}
if(visited[newX][newY][isBroken]){
continue;
}
//아직 벽안부쉈고, 지금 탐색할 곳이 벽일 경우
if( isBroken==0 && map[newX][newY]==1) {
queue.add(new int[]{newX,newY,distance+1,1});
visited[newX][newY][1]=true;
}
//벽 부쉈고, 지금 탁샐할 곳이 벽일경우
else if(isBroken==1 && map[newX][newY]==1){}
//나머지일 경우일 경우
else{
queue.add(new int[]{newX,newY,distance+1,isBroken});
visited[newX][newY][isBroken]=true;
}
}
}
// 큐가 다비워졌는데도, 즉 가능한 모든 탐색을 했는데도 중간에 정답이 안나왔으면
// 갈수가 없으므로 -1 리턴
return -1;
}
}
설명
평범한 최단거리를 찾는문제에서, 벽이 존재하며 1 번만 부술수 있다는 조건이 생긴 문제이다.
최단거리를 찾는 문제이기때문에, bfs로 격자판을 탐색하기로 하였다.
일반적인 미로에서 최단거리 찾는 문제와 다른 점이라면, 벽이라는 장애물이 생겼기 떄문에
어느 한 지점(예를 들어 좌표 [2,4]라고하자)에 도달하는 최단 경로의 수가 1가지가 아니라 2가지이다.
경로의 수라 하니 헷갈릴 수 있겠다.
왜냐면 최단경로의 수 자체는 여러개 있을수도 있기 때문이다.
정확히는 경로의 조건(특성)의 수라고 표현해야 겠다.
즉 [2,4] 에 최단거리로 도달했을때 (bfs를 돌렸을때 해당 좌표에 처음도달했을때) , 그 경로가 벽을 부쉈다는 특성과 벽을 부수지 않았다는 특성 을 가진 두가지의 최단 경로가 있다는 것이다.
따라서
앞서 벽을 부수고 [2,4]로 제일 빨리 도달한 경로 => visited[2][4][1]
앞서 벽을 부수지 않고 [2,4]로 제일 빨리 도달한 경로 => visited[2][4][0]
이렇게 방문처리를 해야한다.
이제 방문처리는 설명했고, 로직을 살펴보자.
우리가 길을 가면서 겪는 모든 경우의 수는 4가지로 나눌 수 있다
- 이미 벽을 부쉈고, 지금 탐색할 곳이 벽인 경우
- 이미 벽을 부쉈고, 지금 탐색할 곳이 벽이 아닌 경우
- 아직 벽을 안부쉈고, 지금 탐색할 곳이 벽인 경우
- 아직 벽을 안부쉈고, 지금 탐색할 곳이 벽이 아닌 경우
이렇게 4가지로 나눠져있다.
- 이미 벽을 부섰고, 지금 탐색할 곳이 벽인 경우
아무 것도 하지 않고 넘긴다
- 이미 벽을 부쉈고, 지금 탐색할 곳이 벽이 아닌 경우
새로 탐색한 곳을 Queue에 넣는데, 탐색한 거리를+1, 벽을 부쉈음을 표현하는 1을 그대로 가지고 간다.
- 아직 벽을 안부쉈고, 지금 탐색할 곳이 벽인 경우
새로 탐색한 곳을 Queue에 넣는데, 탐색한 거리를+1, 벽을 부쉈는지의 유무를 바꾼다(0에서 1로)
- 아직 벽을 안부쉈고, 지금 탐색할 곳이 벽이 아닌 경우
새로 탐색한 곳을 Queue에 넣는데, 탐색한 거리를+1, 벽을 부수지 않았음을 표현하는 0을 그대로 가지고 간다.
이렇게 가능한 경우를 모두 나누어 각 형태에 맞는 처리를 하면 된다.
그리고 이때, 앞서 벽을 부수든 부수지 않든, 지금 탐색할 곳이 벽이 아니라면 해야되는 처리는 똑같다.
그리고 최종적으로, 이렇게 계속 Queue에 새로운 좌표를 추가하다가, 그 좌표가 맨 끝값이라면,
그때 처음 도달한 거리값을 리턴하면 된다.
만약 큐가 빌떄까지 계속 돌았는데도 맨 끝에 도달할수 없으면, 절대 갈수가 없다는 의미이므로 -1을 리턴한다.