2206번 벽 부수고 이동하기

문제

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

접근 방식

벽 하나씩 깨보면서 bfs 돌려보면 시간 초과로 안된다.
정확히 8개월 전의 내가 그렇게 시도한 걸 발견❕

맵 자체도 최대 1000 * 1000이기 때문에, 하나의 BFS로 끝내는 게 좋다. 1도 0도 큐에 집어넣되, 1은 한번만 넣는다는 점을 염두에 두고 넣으면 된다.

그러므로 큐에 담기는 건 (현재 좌표 x, y, 거리 d, 벽을 뚫은 적 있는지 flag)다.

visited 처리도 신경 써야 하는데, 같은 곳을 벽을 뚫고 방문할 수도, 벽을 뚫지 않고 우회해서 방문할 수도 있기 때문에 따로 관리해줘야 한다.

코드

from collections import deque


n, m = map(int, input().split())
board = [input() for _ in range(n)]


def bfs():
    queue = deque([(0, 0, 1, False)])
    # 벽을 뚫고 방문한 전적이 있냐 / 벽을 뚫지 않고 방문한 전적이 있냐
    visited = [[[False] * 2 for _ in range(m)] for _ in range(n)]

    while queue:
        cx, cy, d, flag = queue.popleft()

        if (cx, cy) == (n - 1, m - 1):
            return d

        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            if 0 <= cx + dx < n and 0 <= cy + dy < m and not visited[cx + dx][cy + dy][int(flag)]:
                if flag and board[cx + dx][cy + dy] == '1':
                    continue
                queue.append((cx + dx, cy + dy, d + 1, flag or board[cx + dx][cy + dy] == '1'))
                visited[cx + dx][cy + dy][int(flag)] = True

    return -1


print(bfs())