[백준] 2206: 벽 부수고 이동하기

문제이해

맵에는 이동할 수 있는 0과, 전체 경로중 딱 한 번만 이동할 수 있는 벽인 1이 있다. (0, 0)에서 맨 아래 오른쪽으로의 최단거리를 구하는 문제이다. 

계획

먼저 벽을 부순 경우와 안 부순 경우인 두 경우를 다르게 생각해야 하는 것이 핵심 개념이다. 만약 벽을 이미 부수었는지 여부 상관없이 최단 거리를 구하게 되면 다음과 같은 경우는 -1이 출력 되게 된다.

01000
01110
01000
00010
01111
00110

벽을 부셨는지 상관하지 않고 파란색 칸까지의 최단거리는 노란색을 따라간다. 하지만 노란색 경로는 이미 벽을 부셨으므로 파란색 칸에서 더 이상 정답으로 이동할 수 없다. 따라서 파란색 칸에는 노란색 경로뿐만 아니라 한 번도 벽을 부수지 못한 경로(초록색)도 저장되어야 한다.

따라서 칸에 방문했는지 확인 할때 벽을 부순 경우와 벽을 안 부순 경우를 구분하여 확인해야 한다.

 

계획수행

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
table = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
v = [[[-1, -1] for _ in range(m)] for _ in range(n)]	#첫번째 -1은 벽을 부수지 않은 경우,
							#두번째 -1은 벽을 한번 부순 경우이다.

q = deque()
q.append([0, 0, 0])
v[0][0][0] = 1			#처음은 당연히 벽을 부수지 않았으므로 첫번째 -1을 1로 바꿔준다.

while len(q) > 0:
    t = q.popleft()
    r = [0, 0, -1, 1]
    c = [-1, 1, 0, 0]

    for i in range(4):
        nr = t[0] + r[i]
        nc = t[1] + c[i]

        if 0<=nr<n and 0<=nc<m:
            if table[nr][nc] == '0' and v[nr][nc][t[2]] == -1:	#벽이 아니고, 벽을 부순경우와 안부순 경우를 다르게 비교한다(t[2])
                v[nr][nc][t[2]] = v[t[0]][t[1]][t[2]] + 1
                q.append([nr, nc, t[2]])	#확인해야할 좌표와, 벽을 부순 경우인지 저장
            elif table[nr][nc] == '1' and v[t[0]][t[1]][0] != -1 and v[nr][nc][1] == -1:
                v[nr][nc][1] = v[t[0]][t[1]][0] + 1
                q.append([nr, nc, 1])		#벽이라면 현재 벽을 안부순 경우고, 이미 이동안했다면
            

if v[-1][-1][0] == -1 and v[-1][-1][1] == -1:
    print(-1)
elif -1 in v[-1][-1]:
    print(max(v[-1][-1]))
else:
    print(min(v[-1][-1]))

 

느낀점

처음에 벽을 부순경우와 안 부순 경우를 다르게 비교해야 하는지 몰라서 좀 헤맸다. 벽을 부순경우와 안부순경우를 따로 생각해야 하는 게 이문제의 중요한 부분인 것 같다.