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

문제

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

2206번: 벽 부수고 이동하기

 

풀이

visited는 앞서 방문한 위치를 체크하여 재방문하지 않도록 하고, 경로 및 이동 거리를 저장합니다.

visited를 벽 부수기 전후로 나누어 체크합니다.

• visited[x][y][0] : 벽 부수기 전 경로
• visited[x][y][1] : 벽 부수기 후 경로

이동할 위치의 이동 거리를 현재 위치의 이동 거리에 1을 더해 구합니다.

 

코드

파이썬

import sys
from collections import deque

input = sys.stdin.readline

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

N, M = map(int, input().split())
board = [list(map(int, list(input().rstrip()))) for _ in range(N)]


def BFS():
    queue = deque()
    visited = [[[0] * 2 for _ in range(M)] for _ in range(N)]
    visited[0][0][False] = 1
    queue.append((0, 0, False))
    while queue:
        x, y, c = queue.popleft()
        if (x, y) == (N - 1, M - 1):
            return visited[x][y][c]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if board[nx][ny] == 0 and not visited[nx][ny][c]:
                    visited[nx][ny][c] = visited[x][y][c] + 1
                    queue.append((nx, ny, c))
                elif board[nx][ny] == 1 and not c:
                    visited[nx][ny][True] = visited[x][y][c] + 1
                    queue.append((nx, ny, True))
    return -1


print(BFS())