[Python]2206. 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

---

 

from collections import deque
 
dr = ((-1,0), (1,0), (0,-1), (0,1))
 
def bfs(y,x,k):
    global n, m
    queue = deque()
    queue.append((y,x,k)) # k 는 전체 맵에서 어떤 벽이 한번 부숴진 상태를 나타낸다. k=0 부숴지기 전 k=부숴진 후
    dist[y][x][k] = 1
    while queue:
        curr_y, curr_x, status = queue.popleft()
        for d in dr:
            next_y, next_x = curr_y+d[0], curr_x+d[1]
            if 0<=next_y<n and 0<=next_x<m:
                if MAP[next_y][next_x] == 0 and dist[next_y][next_x][status] == 0: # 평지이고 주변 벽이 (부숴지기 전/부숴진 후) 방문한적 없다면
                        dist[next_y][next_x][status] = dist[curr_y][curr_x][status]+1
                        queue.append((next_y,next_x,status))
 
                if status == 0: # 평지든 벽이든 부숴진 벽이 없을 때
                    if MAP[next_y][next_x] == 1 and dist[next_y][next_x][status + 1] == 0: # 벽이고 벽이 부숴진적 없다면(= 부숴지고 방문안했다면)
                            dist[next_y][next_x][status+1] = dist[curr_y][curr_x][status] + 1
                            queue.append((next_y, next_x, status+1))
 
n, m = map(int, input().split())
MAP = [list(map(int, input())) for _ in range(n)]
dist = [[[0]*2 for _ in range(m)] for _ in range(n)]
bfs(0,0,0)
 
if dist[n-1][m-1][0] != 0 and dist[n-1][m-1][1]  != 0: # 부숴지기 전과 후를 비교해서 작은 것을 출력
    print(min(dist[n-1][m-1]))
elif dist[n-1][m-1][0] != 0: # 부숴지기 전만 값이 있다면 부숴지기 전만 출력
    print(dist[n-1][m-1][0])
elif dist[n-1][m-1][1] != 0: # 부숴진 후만 값이 있다면 부숴진 후만 출력
    print(dist[n-1][m-1][1])
else:
    print(-1) # 둘다 값이 없다면 도달할 수 없는 것이므로 -1 출력
 
'''
보충설명
dist[i][i][0] = 벽이 부숴진 것 없이 자기 자신의 위치에 도달하는 최단경로
dist[i][i][1] = 벽이 부숴진 후 자기 자신의 위치에 도달하는 최단경로
dist[i][j][0] = 벽이 부숴진 것 없이 i에서 j 위치에 도달하는 최단경로
dist[i][j][1] = 벽이 부숴진 후 i에서 j 위치에 도달하는 최단경로
'''
'''
# input
6 9
010001000
010001010
010101010
010101000
010101010
000100010

# ouput
18
'''
'''
출처: https://www.acmicpc.net/board/view/27386
"현재 상태" 자체를 큐에 넣어서 문제를 풀어야 합니다. 
즉, 어떤 좌표에 있는가 뿐만 아니라, "여기까지 오면서 벽을 부순 적이 있는가" 여부를 함께 큐에 저장해서 탐색하고, 
각각을 별개로 방문 체크해줘야 하는 문제입니다. visited[x][y]가 아니라, visited[x][y][벽을 부순 적이 있는가?] 가 되어야 합니다.
'''