백준 1261번 : 알고스팟 in Python

1261번: 알고스팟

 

www.acmicpc.net

이 문제는 미로가 주어질 때 맨 왼쪽 위 지점(좌표로 치면 (1, 1) 지점)에서 출발해 맨 오른쪽 아래 지점(좌표로 치면 (N, M) 지점)으로 이동하기 위해서 최소 몇 개의 벽을 부수어야 하는지를 구하는 문제이다.

우선 벽을 부술 수 없는 경우에는 (1, 1) 지점에서 (N, M) 지점으로 가는 최단 경로를 찾기 위해 BFS, 즉 너비 우선 탐색을 이용했다. 그러므로 벽을 최대한 덜 부수기 위해서, 즉 최대한 벽이 없는 경로를 따라가기 위해서 BFS를 이용한다. 

여기에 더해, 벽을 부수는 경우 역시 고려해야 하는데, 여기서는 dynamic programming을 활용한다. 미로 내 각 좌표마다 그 좌표까지 도달하기 위해 부숴야 하는 벽의 갯수의 최솟값을 저장하는 N*M 행렬 dp를 만들고, 미로에 대해 BFS를 수행하는 중에 빈 좌표의 경우에는 지금까지 벽을 부순 총 횟수, 벽을 만나는 경우에는 해당 좌표의 벽을 부순 뒤의 벽을 부순 총 횟수와 현재 dp에 저장되어 있는 값을 비교해 더 작은 값을 dp에 저장하는 방식으로 진행한다. 이때 초기값은 INF로 해 해당 좌표를 아직 방문하지 않았음을 나타낸다. 그러면 BFS를 끝냈을 때 dp 내 각 entry에는 해당 좌표까지 도달하는데 부숴야 할 벽의 갯수의 최솟값이 저장된다. 따라서 dp[N-1][M-1]을 출력하면 된다.

이를 코드로 구현하면 다음과 같다.

from collections import deque
import sys
M, N = map(int, input().split())
maze = []
for _ in range(N):
    maze.append(list(input()))
# 각 좌표까지 도달하는데 부숴야 할 벽의 갯수의 최솟값을 저장하는 행렬
dp = [[sys.maxsize]*M for _ in range(N)]
# BFS를 위해 동, 서, 남, 북 4방향을 나타내기 위한 배열
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
queue.append([0, 0])
dp[0][0] = 0
# BFS를 실행한다.
while queue:
    x, y= queue.popleft()
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if 0<=next_x<N and 0<=next_y<M:
            # 인접한 방이 빈 방인 경우 지금까지 벽을 부순 횟수가 
            # 이전에 인접한 방까지 도달하기 위해 벽을 부순 횟수보다 작은지 고려하고
            # 만약 작은 경우 이를 인접한 방의 벽을 부순 횟수의 최솟값으로 수정한다.
            # 그리고 이를 바탕으로 다른 방의 벽을 부순 횟수를 수정하기 위해 queue에 인접한 방을 추가한다.
            if maze[next_x][next_y] == '0' and dp[next_x][next_y] > dp[x][y]:
                dp[next_x][next_y] = dp[x][y]
                queue.append([next_x, next_y])
            # 인접한 방이 벽으로 이루어진 경우 지금까지 벽을 부순 횟수 + 1 이
            # 이전에 인접한 방까지 도달하기 위해 벽을 부순 횟수보다 작은지 고려하고 
            # 만약 작은 경우 위와 같은 과정을 거친다.
            elif maze[next_x][next_y] == '1' and dp[next_x][next_y] > dp[x][y] + 1:
                dp[next_x][next_y] = dp[x][y] + 1
                queue.append([next_x, next_y])
print(dp[N-1][M-1])