[백준], 2206번, 벽 부수고 이동하기 (파이썬)

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제입력1

6 4
0100
1110
1000
0000
0111
0000

예제출력1

15

예제입력2

4 4
0111
1111
1111
1110

예제출력2

-1

풀이

from collections import deque

n,m = map(int,input().split()) #행렬 크기 입력
maze = [list(map(int,input())) for _ in range(n)] #미로 입력 
def bfs(): #bfs 로 구현
    queue=deque() #좌표와 찬스를 기록할 큐
    visited = [[[0]*2 for _ in range(m)] for _ in range(n)] #방문한 값을 저장할 리스트
                                                            #벽뿌수기 찬스 유무 구별을 위해 3차원배열로 선언
    
    dx, dy = [-1,1,0,0],[0,0,-1,1] #x,y 이동하는 경우의 수
    visited[0][0][True] = 1 #문제 조건에 맞게 첫번째 방문 카운트
    queue.append([0,0,True]) #0,0 찬스(ㅇ) 큐에 삽입
    while queue: #큐가 빌때까지 반복
        x,y,chance = queue.popleft() #선입선출 빼주기
        if x==n-1 and y==m-1: #x,y가 (n,m)행렬의 마지막 좌표라면
            return visited[x][y][chance] #함수 종료 후 마지막 좌표값 반환
                                         #bfs 라면 가장 먼저 도착한 값이 최소값일테니까
                                
        for i in range(4):#상하좌우 탐색
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m: #리스트(행렬) 인덱스 범위안에 들어가야하므로    
                if chance and maze[nx][ny]: #찬스가 있고 미로가 벽이라면
                    visited[nx][ny][False]=visited[x][y][True]+1 #찬스(x) 리스트에 이전 이동값+1
                    queue.append([nx,ny,False]) #찬스 없애고 append
                elif not maze[nx][ny] and not visited[nx][ny][chance]: #인덱스 안에서 벽이 없는 공간으로 움직일 때
                    visited[nx][ny][chance]=visited[x][y][chance]+1
                    queue.append([nx,ny,chance])
    return -1 #큐가 빌때까지 반복을 했지만 마지막 좌표값 반환을 하지 못했을 때
              #마지막 좌표값을 반환하지 못했다는 것은 목적지에 도착하지 못했다는 뜻

print(bfs())

문제해설

3차원배열로 생각해도 되고, 아니면 2차원 배열 2개를 생성해서 풀어도 됩니다. (개인적으로는 2차원 배열 2개 생성해서 푸는게 더 가독성 있는 듯)

벽 뿌수기라는 찬스가 있는 visited, 벽 뿌수기 찬스를 쓴 visited

2가지 리스트를 만들어 큐에 넣으면 간단하게 풀 수 있습니다.

하지만, 문제를 풀다보면 각자 배열에서 거꾸로 올라가는 경우도 생기는데

이는 무시해도 됩니다. bfs 는 최단경로를 보장하기 때문에 최초에 리스트값에 들어간 값이 최단경로가 된다는 사실을 잊으면 안됩니다.