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

📚문제: #2206 벽 부수고 이동하기(Gold 3)

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

아이디어 및 구현

• 벽을 부수지 않았을 때, 벽을 1개만 부쉈을 때를 구분하여 맵의 (r,c)에 도달하는 최소거리를 저장하는 리스트(visited)를 생성한다.

# visited[0][r][c] = 벽을 부수지 않았을 때 (r,c)에 도달하는 최솟값
# visited[1][r][c] = 벽을 1개 부쉈을 때 (r,c)에 도달하는 최솟값
visited = []

for _ in range(2):
    
    temp = [[0] * M for _ in range(N)]
    
    visited.append(temp)

• BFS Algorithm을 작성한다. 큐에서 자료를 꺼냈을 때 벽을 부순횟수에 따라 리스트(visited)에 다르게 저장된다.
  • 현재까지 벽을 부수지 않았을 때
    • 이동하려는 좌표가 빈 공간이면 벽을 부수지 않고 이동한다.(부순 벽 0개 유지)
    • 이동하려는 좌표가 벽이면 벽을 1개 부수고 이동한다.(부순 벽 1개로 갱신)
  • 현재까지 벽을 1개 부쉈을 때
    • 이동하려는 좌표가 빈 공간이면 벽을 부수지 않고 이동한다.(부순 벽 1개 유지)
    • 이동하려는 좌표가 벽이면 이동할 수 없으므로 무시한다.

def BFS(start):
    
    # 4방향
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    
    # 큐 생성 (벽을 부순 횟수, 좌표)
    queue = deque([[0, start]])
    
    # 시작지점 초기화
    visited[0][0][0] = 1
    visited[1][0][0] = 1
    
    # 큐가 빌 떄까지 반복
    while queue:
        
        # 벽을 부순 횟수, 현재 좌표
        wall, cur = queue.popleft()
        
        cur_r, cur_c = cur
        
        # 4방향
        for i in range(4):
            
            move_r, move_c = cur_r + dr[i], cur_c + dc[i]
            
            # 주어진 맵 크기를 벗어나지 않으면서 방문하지 않은 지점일 때
            if 0 <= move_r <= N-1 and 0 <= move_c <= M-1 and visited[wall][move_r][move_c] == 0:

                # 이동 가능할 때
                if graph[move_r][move_c] == 0:
                    
                    visited[wall][move_r][move_c] = visited[wall][cur_r][cur_c] + 1
                    queue.append([wall, [move_r, move_c]])
                    
                # 벽일 때
                elif graph[move_r][move_c] == '*':
                    
                    # 기존에 부순 벽이 없다면
                    if wall == 0:
                        
                        # 벽을 새롭게 1개 부순다.
                        visited[wall+1][move_r][move_c] = visited[wall][cur_r][cur_c] + 1
                        queue.append([wall+1, [move_r, move_c]])
                    
                    # 기존에 부순 벽이 1개 있다면 더 이상 부술 수 없으므로 무시한다.
                    else:
                        
                        continue

전체 코드

import sys
from collections import deque

def BFS(start):
    
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    
    queue = deque([[0, start]])
    
    visited[0][0][0] = 1
    visited[1][0][0] = 1
        
    while queue:
        
        wall, cur = queue.popleft()
        
        cur_r, cur_c = cur
        
        for i in range(4):
            
            move_r, move_c = cur_r + dr[i], cur_c + dc[i]
            
            if 0 <= move_r <= N-1 and 0 <= move_c <= M-1 and visited[wall][move_r][move_c] == 0:

                if graph[move_r][move_c] == 0:
                    
                    visited[wall][move_r][move_c] = visited[wall][cur_r][cur_c] + 1
                    queue.append([wall, [move_r, move_c]])
                    
                elif graph[move_r][move_c] == '*':
                    
                    if wall == 0:
                        
                        visited[wall+1][move_r][move_c] = visited[wall][cur_r][cur_c] + 1
                        queue.append([wall+1, [move_r, move_c]])
                    
                    else:
                        
                        continue
                    
N, M = map(int, sys.stdin.readline().split())

graph = []

visited = []

for _ in range(2):
    
    temp = [[0] * M for _ in range(N)]
    
    visited.append(temp)
    
for _ in range(N):
    
    graph.append(list(map(int, sys.stdin.readline().rstrip())))

for i in range(N):
    
    for j in range(M):
        
        if graph[i][j] == 1:
            
            graph[i][j] = '*'

s = [0,0]

BFS(s)

if visited[0][N-1][M-1] > 0 and visited[1][N-1][M-1] > 0:
    
    print(min(visited[0][N-1][M-1], visited[1][N-1][M-1]))

elif visited[0][N-1][M-1] == 0 and visited[1][N-1][M-1] == 0:
    
    print(-1)

else:
        
    print(max(visited[0][N-1][M-1], visited[1][N-1][M-1]))