[백준] 2206 : 벽 부수고 이동하기
용어정리
- 벽을 한번 뚫고 온 상태를 depth 1, 벽을 뚫고 오지 않은 상태를 depth 0라고 정의합니다.
- (0,0) → (N-1, M-1) 경로라고 생각합니다.
생각하지 못한 Case
같은 정점을 서로 다른 depth로 방문할 수 있다. 그러므로 방문 체크가 ‘독립적으로’ 진행되어야 한다
다음과 같은 3 X 3케이스를 생각해보자
1
2
3
4
5
0 ─── 0 ─── 1
│ │ │
1 ─── 0 ─── 1
│ │ │
1 ─── 1 ─── 0
(0,0)에서 (2,2)를 방문하기 위해서는, 반드시 다음의 2가지 케이스 밖에 없다.
1
2
3
4
5
0 ─── 0
│
0 ─── 1
│ │
1 ─── 0
이때, (1,1)에 집중하자. 원래 (1,1)에 도달하는 방법은 2가지 경로가 있다.
- (1,0)을 거치는 경우
- (0,1)을 거치는 경우
1
2
3
4
5
0 ─── 0 1
│ │
1 ─── 0 1
1 1 0
depth를 고려하지 않고 int visit = [1001][1001]과 같이 선언한 경우를 가정해보자. (방문체크가 독립적으로 이루어지지 않는 상태) 이때 (1)번 경로를 먼저 탐색한다고 가정한다. 그렇다면 (1,1)에 최단거리 2(depth 1 경로)를 갱신할 것이다. 문제는 여기서 발생한다. 이 경로로는 (1,2)나 (2,1)에 있는 벽을 뚫고 (2,2)에 도달하는 것이 불가능하다.
그러나, (2)번 경로를 먼저 탐색한다고 가정하자. 그렇다면 (1,1)에 최단거리 2 (depth 0) 경로가 갱신될 것이다. 이 경로로는 (2,2)에 도달하는 것이 가능하다.
위의 케이스에서 보듯, 방문 채크는 독립적으로 진행되어야 한다.
마찬가지의 원리로, 최단 경로 배열 또한 독립적으로 구성되어야 한다. 해당 정점에서 depth 1 최단거리 < depth 0 최단거리인데, 결론적으로는 depth 0 경로를 통해서만 도달 가능한 경우가 있을 수 있기 때문이다. 이때 두 경로의 최단거리가 구분되어야 제대로 된 결괏값이 나온다. (구분되지 않으면 경로는 depth 0인데, depth 1 최단거리를 이용한 값이 나올 수 있다.)
예를 들면 다음과 같다.
1
2
3
4
5
6
7
8
9
0 ─── 0 ─── 0 ─── 1 ─── 1
│ │ │ │ │
1 ─── 1 ─── 0 ─── 1 ─── 1
│ │ │ │ │
1 ─── 0 ─── 0 ─── 1 ─── 1
│ │ │ │ │
1 ─── 0 ─── 1 ─── 1 ─── 1
│ │ │ │ │
1 ─── 0 ─── 0 ─── 1 ─── 0
(3,2)에 위치한 1이 (4,2)의 0 정점이 최단거리를 갱신하는 것이 가능하다. 실제 최단 거리는 이 경로를 이용하지 않지만, 최단 경로 배열이 구분되지 않으면 (3,2)가 (4,2)에 갱신한 최단 거리가 (4,4) 까지의 최단 거리 계산에 이용될 위험이 있다.
따라서 코드는 다음과 같아야 한다.
1
2
int dist[1001][1001][2];
int visit_arr[1001][1001][2];