[백준] 2206번 벽 부수고 이동하기 - 파이썬(Python)

문제 (링크)

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

2206번: 벽 부수고 이동하기

 

나의 풀이

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for _ in range(n):
    row = list(str(input().rstrip()))
    graph.append(list(map(int, row)))

# 3차원 배열 사용 -> visited[x][y][z], z = 0 or 1로 기록
# z = 0이면 벽을 뚫지 않고 간 경우, z = 1이면 벽을 뚫고 간 경우
moves = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1]
]
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]

def bfs():
    q = deque()
    q.append([0, 0, 0])
    visited[0][0][0] = 1

    while q:
        x, y, w = q.popleft()
        
        # 목표지점 도달 시 해당 위치까지의 거리 리턴
        if x == n - 1 and y == m - 1:
            return visited[x][y][w]

        for move in moves:
            nx, ny = x + move[0], y + move[1]

            if 0 <= nx < n and 0 <= ny < m:
                # 현재 위치로 이동할 수 있고, 아직 방문하지 않았다면
                if graph[nx][ny] == 0 and visited[nx][ny][w] == 0:
                    visited[nx][ny][w] = visited[x][y][w] + 1
                    q.append([nx, ny, w])
                
                # 현재 위치가 벽이고, 벽을 아직 부수지 않았다면
                elif graph[nx][ny] == 1 and w == 0:
                    visited[nx][ny][w + 1] = visited[x][y][w] + 1
                    q.append([nx, ny, w + 1])
    
    # 목표지점까지 도달하지 못한다면 -1 리턴
    return -1

print(bfs())

코드 설명 및 풀이법

BFS문제 다 똑같지라며 오만방자하던 나에게 alert를 해준 아주 소중한 문제였다.

 

일반적인 그래프 탐색에서 "벽을 단 한 번 뚫을 수 있다"는 심플한 조건이 하나 추가되었지만, 이를 실제로 구현하는 것은 쉽지 않았다.

 

N과 M의 범위가 1 이상 1000 이하이기 때문에 브루트포스 방식도 불가능했고, 최단거리를 만들기 위한 벽을 찾는 방법을 찾는 것도 쉽사리 떠오르지 않았다.

 

모든 작업을 한 번의 BFS 탐색을 통해 처리해야했기 때문에, 최적의 벽을 '탐색'하는 것보다는 '기록'하는 방식이 필요했다.

 

그리고 3차원 배열을 통해서 이 문제를 해결할 수 있었다.

 

visited에는 이미 우리에게 친숙한 2차원 배열의 각 인덱스 [x][y]뿐 아니라 w라는 값을 하나 더 만들어서 (x, y)까지 오는 과정에서 벽을 뚫은 경우와 그렇지 않고 온 경우를 모두 기록해준다. (각각 1번 인덱스와 0번 인덱스에 기록)

 

다시 말해, visited[x][y][0]에 (x, y)까지 벽을 뚫지 않고 왔을 때 걸린 거리(시간)을 기록해준다.

 

반대로, visited[x][y][1]에는 (x, y)까지 오는 데 벽을 한 번이라도 뚫고 온 경우 걸린 거리(시간)을 기록해준다.

 

이는 시각적으로, 가로 세로가 각각 n과 m이고, 높이가 2층짜리인 배열을 생각해보면 쉽게 이해할 수 있다.

 

3차원 배열에서 벽을 뚫지 않는 경우를 1층, 뚫은 경우를 2층이라고 가정하면, (0, 0)에서 시작해서 벽이 없는(이동할 수 있는 공간) 공간으로 BFS로 이동하면서 현재 위치에서 인접한 벽이 있다면 그 곳을 뚫고 2층으로 보내버려서 그곳에서 거리를 기록하는 것이다.

 

사실 처음에는 이 방식이 쉽사리 이해되지는 않았는데, 한 번 이해하고 나니 다른 문제에서도 다양한 방식으로 사용할 수 있을 것 같은 생각이 든다.

 

좋은 문제였다.