[백준 / 2206] 벽 부수고 이동하기 - Python

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

<풀이>

벽을 하나 부순 map과 벽을 부수지 않은 map을 이용하였다.

 

 

<전체 코드>

from collections import deque

n, m = map(int, input().split())
map = []
for _ in range(n):
    map.append(list(input()))

drow = [-1, 0, 1, 0]
dcol = [0, 1, 0, -1]
map[0][0] = 1
map2 = [i[:] for i in map]

q = deque([[0, 0, 1, 1]])
while q:
    r, c, chance, cnt = q.popleft()
    for i in range(4):
        nr = r+drow[i]
        nc = c+dcol[i]

        if 0 <= nr < n and 0 <= nc < m:
            if chance == 1:
                nxt = map[nr][nc]
                if nxt == '0':
                    map[nr][nc] = cnt+1
                    q.append([nr, nc, 1, cnt+1])
                elif nxt == '1':
                    q.append([nr, nc, 0, cnt+1])

                else:
                    if nxt > cnt+1:
                        map[nr][nc] = cnt+1
                        q.append([nr, nc, 1, cnt+1])

            else:
                nxt = map2[nr][nc]
                if nxt == '0':
                    map2[nr][nc] = cnt+1
                    q.append([nr, nc, 0, cnt+1])

                elif nxt != '1':
                    if nxt > cnt+1:
                        map2[nr][nc] = cnt+1
                        q.append([nr, nc, 0, cnt+1])

ans = map[n-1][m-1]
ans2 = map2[n-1][m-1]
if ans == '0' and ans2 == '0':
    print(-1)
elif ans == '0':
    print(ans2)
elif ans2 == '0':
    print(ans)
else:
    print(min(ans, ans2))