[백준2206번] 벽 부수고 이동하기 / Python3

문제

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

나의 풀이

필자는 처음에 방문 여부를 담는 3차원 배열을 만들어 각각의 정점에서 현재까지의 거리와 벽의 부서짐 여부([x][y][벽의 부서짐 여부])를 저장했다. 그러나 이렇게 확인을 하면 예제로 나오는 것은 결과가 제대로 나왔다.. 그러나 제출을하면 문제를 계속 틀려서 검색을 하여 힌트를 얻었다. 여기서 내가 잘못했던것은 벽이 부서진 상황과 부서지지 않은 상황 모두 상황별로 탐색을 이어가야 되는 것이었다. 내가 한 방법은 벽이 한 번 부서지면 그 상황이 계속 유지되기 때문에 벽이 부서지지 않은 상황으로는 그곳을 더 이상은 지나칠 수가 없는 것이었다. 따라서 3차원 배열을 구성하되 [벽의 부서짐 여부][x][y] 이렇게 하게 되면 벽이 부서진 경우, 그렇지 않은 경우 즉, 두가지의 현재까지의 거리를 저장하는 배열이 생기게 된다.

그리고나서는 다른 bfs를 사용해 미로 최단거리를 탐색하는 문제와 비슷하다. 큐에 x,y,벽의 부서짐 여부를 담아 상하좌우의 경우들을 모두 확인해주면 된다.

if visit[wall][nx][ny] == 0:
    visit[wall][nx][ny] = visit[wall][x][y] + 1

단, 벽이 부서지지 않은 경우에 벽을 만났을 경우를 따로 따져주어야한다.

if visit[wall][nx][ny] == 1 and wall == 0:
  visit[1][nx][ny] = visit[wall][x][y] + 1

이렇게 위와 같이 조건문들을 완성해주고 bfs를 돌려주면 문제를 해결할 수 있다. 주의할 점은 bfs함수 내에서 x == n-1, y == m-1인 경우일 때 visit[wall][x][y]를 반환해주었다. 그러나 이 문제에서는 끝까지 가지 못하는 경우가 있을 수 있기때문에 그러한 경우에는 함수의 반환값이 없게된다. 따라서 출력을 해주는 과정에서 반환값이 None가 나오는 경우에 -1을 출력해주고 그렇지 않은경우 그냥 반환값을 출력해주게끔 해주면 된다.

코드

# 2206번 벽 부수고 이동하기
import sys
from collections import deque

# BFS
def bfs():
    q = deque()
    q.append([0,0,0])
    visit[0][0][0] = 1

    dx = [-1,0,1,0]
    dy = [0,-1,0,1]
    while q:
        tmp = q.popleft()
        x = tmp[0]
        y = tmp[1]
        wall = tmp[2]

        if x == n-1 and y == m-1:
            return visit[wall][x][y]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                if visit[wall][nx][ny] == 0:
                    # 벽이 부서지든 안부서지든 0이면 확인해야함.
                    if map[nx][ny] == '0':
                        visit[wall][nx][ny] = visit[wall][x][y] + 1
                        q.append([nx,ny,wall])
                    # 벽이 부서지지 않은 상황에서 벽을 마주한다면 벽을 부순 상황으로 전환
                    elif map[nx][ny] == '1' and wall == 0:
                        visit[1][nx][ny] = visit[wall][x][y] + 1
                        q.append([nx,ny,1])

# main
n, m = [int(x) for x in sys.stdin.readline().split()]

map = []
for _ in range(n):
    map.append(list(sys.stdin.readline()))

# 벽을 부순 경우, 부수지 않은 경우를 모두 확인해야함.
visit = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(2)]

answer = bfs()
if answer == None:  # 끝까지 가지 못하면 return값이 없음.
    print(-1)
else:
    print(answer)