[백준] 2206번 - 벽 부수고 이동하기 (DFS, BFS) - 결과 포함

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

앞에서 풀었었던 최단 거리에 특정 목표 지점까지 이동하는 문제들과 같은 맥락의 문제이다.

시작 지점은 항상 같은 위치로 정해져 있고 목표 위치만 입력에 따라 변한다.

 

다른 문제들과 다른 점은 벽을 한 번 부술 수 있는 "필살기"가 존재한다는 것이다.

시작점에서 출발해서 목표 위치까지 이동할 때 최단 거리로 갈 수 있다면 이동할 수 없는 위치로 이동할 수 있다.

 

일단 전체적인 문제의 구조는 다른 문제들과 똑같이 구성했다.

한 위치에서 다른 위치로 이동할 때 갈 수 있는 방향, 상, 하, 좌, 우를 미리 정해 놓고 방문한다.

 

범위를 벗어나는 정점은 방문하지 않는다.

이미 방문한 정점도 방문하지 않는다.

만약에 목표 위치에 도달하면 더 이상 진행하지 않고 BFS를 종료하고 최단 거리를 출력한다.

 

문제는 방문한 정점들에 대해 최단 거리를 증가시켜서 기록해야 하며,

방문한 곳이 아닌 벽인 곳을 한 번은 부술수 있어야 한다.

 

일단 최초의 입력 받은 그래프는 수정하지 않는다.

벽에 대한 정보가 있기 때문에 방문한 정점에 대한 정보와 벽의 정보를 중복으로 처리하면 구별이 불가능하다.

 

또한 현재 진행하고 있는 BFS가 벽을 부순 적이 있는 지 체크할 수 있어야 한다.

먼저 한 정점에서 다른 정점으로 이동할 때 만약 벽을 만났고 한 번도 부순적이 없다면

무조건 벽을 부순다.

벽을 만났지만 현재의 경로를 진행하면서 벽을 부순 적이 있다면 무시된다.

이 벽을 부순 기록을 crush라는 변수에 표시하고 이동하는 정점의 위치를 큐에 삽입할 때 함께 삽입한다.

 

즉, 지금 진행하고 있는 이 경로에서는 더 이상 벽을 부술 수 없다는 것을 표시하는 것이다.

만약 벽이 아닌 평범하게 이동이 가능한 위치라면 해당 정점의 위치와 현재의 경로에서 벽을 부순 적이 있는지를

넘겨주면서 거리를 증가시킨다.

정리를 해보면,

현재의 정점 위치와 벽 부수기 사용 여부 확인 -> 이동 가능 or (벽 and 벽 부수기 X) -> 이동, 증가한 카운트 저장

 

목표 위치에 도달할 때까지 위의 과정을 반복하고 가장 먼저 목표 위치에 도달한 경로가 최단 경로이다.

 

[소스코드]

from collections import deque

n, m = map(int, input().split())
graph = []

for i in range(n):
    graph.append(list(map(int, input())))

visited = [[[0] * m for _ in range(n)] for _ in range(2)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(crush, _x, _y):
    queue = deque()
    queue.append([crush, _x, _y])
    visited[crush][_x][_y] = 1

    while queue:
        crush, x, y = queue.popleft()
        if x == n - 1 and y == m - 1:
            print(visited[crush][x][y])
            return 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if visited[crush][nx][ny] == 0:
                if graph[nx][ny] == 1 and crush == 0:
                    queue.append([1, nx, ny])
                    visited[1][nx][ny] = visited[crush][x][y] + 1
                if graph[nx][ny] == 0:
                    queue.append([crush, nx, ny])
                    visited[crush][nx][ny] = visited[crush][x][y] + 1
    print(-1)


bfs(0, 0, 0)