백준 2206: 벽 부수고 이동하기(골드3)

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

---

해당 문제는 3차원 BFS로 풀 수 있었다.

 

풀이 및 접근

1. 일단 문제에서 최솟값을 찾아야한다고 했으니, BFS 사용

2. 여기서는 벽을 부수고 가는 경우와 벽을 부수고 가지 않은 경우가 나누어져있기에 그래프를 여러개 생성

2-1. 벽을 부술 수 있는 경우의 그래프를 전부 그려주기 or 3차원으로 벽을 부수고 가는 경우의 3차원 그래프를 그려주기

 

여기서 물론 두가지 다 가능하다.

 

하지만 첫번째의 경우에는 그래프내에서 '1'이 있는 만큼 BFS를 돌아주어야하기 때문에 시간복잡도가 그만큼 늘어난다고 볼 수 있다.

 

때문에 비교적 시간이 덜 걸리는 3차원 BFS로 해주면 된다.

 

3차원 BFS

위의 사진처럼 총 3개의 그래프가 있다고 생각하면 된다.

 

a. 원본 그래프

b. 벽을 부수지 않고 이동했을때의 그래프

c. 벽을 부수고 이동했을때의 그래프

 

풀이과정

여기서부터 고민하고 생각하는데 오래 걸렸다. 

 

일단 문제를 보면 이동을 했을때 딱 한번만 벽을 부술 수 있다고 되어 있다.

때문에 일단 벽을 부수지 않고 이동했을때는 일반적인 BFS처럼 돌아주면 된다.

 

근데 여기서 만약 처음으로 벽을 부쉈다고 가정하자.

 

if 벽을 부숨

벽을 부수고 칸을 이동했기 때문에 이전 벽을 부수지 않은 칸까지 온거리에 + 1

 

if 벽을 부수지 않음

여기서는 벽을 부수지 않았기 때문에 똑같이 부수지 않은 칸에서 온거리 + 1

 

다음은 앞에서 벽을 부순 경우로 가정해보자.

 

여기서는 이미 벽을 부쉈기 때문에 더이상 다른 차원의 그래프로 이동할 필요 없이 벽을 부수고 이동했을때의 그래프에서 최단거리를 구해주면 된다.

 

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

def bfs():
    queue = deque()
    queue.append((0,0,0))
    move = [[[0,0]for _ in range(M)] for _ in range(N)]
    move[0][0][0] = 1

    while queue:
        x, y, broken = queue.popleft()

        if x == N - 1 and y == M - 1:
            return move[x][y][broken]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                
                if graph[nx][ny] == 1 and broken == 0:
                    move[nx][ny][1] = move[x][y][0] + 1
                    queue.append((nx, ny, 1))

                if graph[nx][ny] == 0 and move[nx][ny][broken] == 0:
                    move[nx][ny][broken] = move[x][y][broken] + 1
                    queue.append((nx, ny, broken))

    return -1

 

벽을 부순그래프로 이동하면 더이상 그래프간의 이동이 필요하지 않지만,
벽을 부수지 않은 경우에는 언제든지 벽을 부순 그래프로 이동할 수 있게 된다.

 

최종 코드

from collections import deque

N, M = map(int, input().split())
graph = [[0] * M for _ in range(N)]
for i in range(N):
    row_data = input().strip()
    for j in range(M):
        graph[i][j] = int(row_data[j])

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

def bfs():
    queue = deque()
    queue.append((0,0,0))
    move = [[[0,0]for _ in range(M)] for _ in range(N)]
    move[0][0][0] = 1

    while queue:
        x, y, broken = queue.popleft()

        if x == N - 1 and y == M - 1:
            return move[x][y][broken]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                
                if graph[nx][ny] == 1 and broken == 0:
                    move[nx][ny][1] = move[x][y][0] + 1
                    queue.append((nx, ny, 1))

                if graph[nx][ny] == 0 and move[nx][ny][broken] == 0:
                    move[nx][ny][broken] = move[x][y][broken] + 1
                    queue.append((nx, ny, broken))

    return -1

print(bfs())