[🥇4 / 백준 2206 / 파이썬] 벽 부수고 이동하기

 

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

 

풀이

 

시작점부터 출구까지 최단거리를 구하되, 벽 한 칸을 부술 수 있을 때의 최단거리를 구하는 문제이다.

본인에겐 공식 난이도 골드 4의 문제치곤 좀 더 어렵게 다가온 문제인 것 같다.

 

맨 처음에는 원시적으로 생각했다.

BFS를 진행하다가 주변에 벽이 존재하고, 벽을 부순 적이 없을 때

해당 벽부터 다시 BFS를 진행하고 다시 원래되로 되돌린 뒤 원래의 BFS를 진행하는 방식으로

답이 나올 때까지 반복하면 어떨까 생각했다.

 

당연 BFS가 아니라 도중에 DFS가 되어 10x10의 맵으로도 시간초과에 걸리게 되었다.

 

 

그렇게 고민하다가 원래의 DFS를 그대로 진행하는 배열과,

벽을 부술 수 있을 때의 방문 배열 두 가지를 만들면 될 것 같다는 생각이 들었다.

 

여기까지는 좋았지만, 추후 코드 작성에 어려움을 느껴 여러 질문글과 블로그를 돌아보며 아이디어를 추합했다.

그 결과, 방문할 좌표를 큐에 넣을 때 벽을 이미 부쉈는지의 여부를 함께 넣는 방법이 가장 좋은 것 같았다.

 

맵 배열은 3차원 배열로 구성했다.

3차원 배열을 구성할 때 잘못하여 같은 포인터의 리스트를 또 불러오는 바람에 욕봤다.

다음엔 이런 실수를 하지 않기를 바란다.

 

from collections import deque
import sys
input = sys.stdin.readline

n,m = map(int,input().split())
# 3차원 배열 구성
mapp = [[],[]]
for i in range(n):
    _ = input().rstrip()
    mapp[0].append(list(map(int,list(_))))
    mapp[1].append(list(map(int,list(_))))
    
dx = [0,1,0,-1]
dy = [1,0,-1,0]
deq,r = deque(),[]

# x,y,부술 수 있는 벽의 수
deq.append((0,0,1))

# 벽이 1이기 때문에 편의상 첫 시작을 2로 하고 마지막에 1을 빼주었다.
mapp[1][0][0] = 2
mapp[0][0][0] = 2

while(deq):
    if mapp[0][n-1][m-1] > 0:
        break
    
    x,y,smashed = deq.popleft()
    for i in range(4):
        a,b = x+dx[i], y+dy[i]
        if n > a >= 0 and m > b >= 0:
            if mapp[smashed][a][b] == 0:
                mapp[smashed][a][b] = mapp[smashed][x][y]+1
                if smashed == 1:
                    mapp[0][a][b] = min(mapp[0][x][y],mapp[1][x][y])+1
                deq.append((a,b,smashed))
            
            if smashed == 1 and mapp[1][a][b] == 1:
                mapp[0][a][b] = mapp[1][x][y]+1
                deq.append((a,b,0))

# BFS가 끝났는데도 출구가 0이면 -1 출력
print(mapp[0][n-1][m-1]-1 if mapp[0][n-1][m-1] > 0 else -1)