2206번. 벽 부수고 이동하기

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

 

 

1. visited를 따로 사용할 필요가 없다. 거리를 나타내는 dist 배열이 0 이상이면 방문한 적이 있다는 뜻이기 때문.

2. dist에 방문 여부를 표시하되, 지금까지 벽을 부순 적 있는 경우와 없는 경우를 따로 체크해야 한다.

벽을 부수지 않고 오다가, 어떤 벽을 만났는데 다른 경로가 한번 부숴서 지나갔다고 거기서 막히면 안 된다. 벽은 각 '경로마다' 한 번씩 부술 수 있기 때문이다. 벽이 아닌 길을 만났을 때도 여기까지 '벽을 부수면서 온 경로'만 방문했다면 이번 경로는 '벽을 부수지 않고 온 유일한 경로'이다.

3. 모든 길을 모두 방문하지 않고 중간에 목적지를 만났으면 리턴하는 것이 좋다. 벽을 부수면서 도착했건, 부수지 않으면서 도착했건 일단 도착했으면 제일 먼저 도착한 것이므로 바로 리턴하면 된다. 또다른 경우를 상정하지 않는다.

 

아, 벽이 0이나 1이 아니라 '0'이나 '1'임에 유의하자.

import sys
import collections


def bfs(start):
    queue = collections.deque()
    queue.append(start)
    dist[start[0]][start[1]][0] = 1

    while queue:
        r, c, wallBreak = queue.popleft()  # wallBreak=지금껏 벽을 부순 적이 있는가?
        if r == n-1 and c == m-1:
            return dist[r][c][wallBreak]  # BFS는 처음 목적지에 도착하면 그것이 최단경로
        for nR, nC in [[r+1, c], [r-1, c], [r, c+1], [r, c-1]]:
            if 0 <= nR < n and 0 <= nC < m:
                if dist[nR][nC][wallBreak] > 0:  # 이전에 같은 상태에서 방문한 적이 있으면 방문하지 않음
                    continue
                if board[nR][nC] == '0':  # 벽이 뚫려있으면
                    dist[nR][nC][wallBreak] = dist[r][c][wallBreak] + 1  # 단순하게 부모 노드+1
                    queue.append([nR, nC, wallBreak])
                elif board[nR][nC] == '1' and wallBreak == 0:  # 벽이 막혀 있고, 이전에 뚫고 온 적이 없으면
                    dist[nR][nC][1] = dist[r][c][wallBreak] + 1
                    queue.append([nR, nC, 1])
    return -1


n, m = map(int, sys.stdin.readline().split())
board = []
for _ in range(n):
    board.append(sys.stdin.readline().rstrip())
dist = [[[0, 0] for _ in range(m)] for _ in range(n)] # [non-break distance, break distance]

print(bfs([0, 0, 0]))  # 큐의 초기값. row, col, break_or_not