[Python] boj no. 2665 : 미로만들기

Problem

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

Idea

현재 위치에서 흰 방으로 이동할 때는 가중치가 0이고 검은 방으로 이동할 때는 가중치가 1인 최단경로 문제이다. 가중치가 0 또는 1이므로 다익스트라 알고리즘이 아닌 0-1 bfs를 이용하여 풀었다. 힙을 이용한 다익스트라 알고리즘의 시간 복잡도가 O(E logV)인 반면 0-1 bfs로 구현할 경우 O(V+E)의 시간복잡도로 해결할 수 있기 때문이다.

우선 시작 시점을 제외한 모든 지점까지의 거리를 maxsize로 설정해주었다. 이후 현 위치에서 네 방향으로 탐색하되 다익스트라 알고리즘과 같이 현재 탐색 지점까지의 거리가 지금까지 계산된 거리보다 작을 경우에만 탐색하도록 하였다. 이 때 흰 방일 경우 appendleft를, 검은 방일 경우 append를 해주었다.

Code

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
maze = [list(map(int, input().rstrip())) for _ in range(n)]
wall = [[sys.maxsize for _ in range(n)] for _ in range(n)]

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

dq = deque()
dq.append((0, 0))
wall[0][0] = 0

while dq:
    py, px = dq.popleft()
    
    for i in range(4):
        ny, nx = py+dy[i], px+dx[i]
        if 0 <= ny < n and 0 <= nx < n and wall[py][px] < wall[ny][nx]:
            if maze[ny][nx] == 1:
                wall[ny][nx] = wall[py][px]
                dq.appendleft((ny, nx))
            else:
                wall[ny]
                wall[ny][nx] = wall[py][px] + 1
                dq.append((ny, nx))
                
print(wall[-1][-1])

Comment