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

문제

2206번: 벽 부수고 이동하기

 

문제 풀이

 그래프를 탐색하는데 이동할 수 없을 경우 벽 하나를 부수고 탐색을 이어갈 수 있다. 즉, 벽 하나를 부술 경우 가장 최단 경로로 (N, M)에 도착하는 경우를 반환하는 문제이다. 보통 최단 거리를 구할 때, 2차원 배열을 생성하여 이동한 거리를 중첩시켜며 앞으로 나아가며 목적지에 도착한 경우 탐색을 종료한다. 문제에서는 벽을 부순 경우와 부수지 않은 경우 2가지의 경우의 수가 존재하기에 기존에 거리를 중첩하는 방식이 아닌 3차원 배열을 통해 부순 경우에 대한 경우의 수도 따로 중첩시킨다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y, w):
    return 0 <= x < n and 0 <= y < m and not visited[x][y][w]


def bfs(start):
    q = deque([start])
    dirs = ((-1, 0), (0, 1), (1, 0), (0, -1))

    while q:
        cur_x, cur_y, wall = q.popleft()
        dist = visited[cur_x][cur_y][wall] + 1

        if [cur_x, cur_y] == [n - 1, m - 1]:
            return visited[cur_x][cur_y][wall]

        for x, y in dirs:
            next_x, next_y = cur_x + x, cur_y + y
            if visitable(next_x, next_y, wall):
                if not graph[next_x][next_y]:
                    visited[next_x][next_y][wall] = dist
                    q.append((next_x, next_y, wall))
                elif not wall:
                    visited[next_x][next_y][not wall] = dist
                    q.append((next_x, next_y, not wall))

    return -1


if __name__ == '__main__':
    n, m = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().strip())) for _ in range(n)]
    visited = [[[0, 0] for _ in range(m)] for _ in range(n)]
    visited[0][0] = [1, 1]
    print(bfs((0, 0, 0)))