알고리즘: 백준 2665번 미로만들기 (feat.python)

 

2665번: 미로만들기

 

 

import sys
import copy
import heapq

read = sys.stdin.readline
n = int(read())
maze = []
for i in range(n):
    maze.append(list(map(int, read().strip())))
visit = copy.deepcopy(maze)


def bfs():
    hq = []
    heapq.heappush(hq, [0,0,0])
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    while hq:
        cnt, cx, cy = heapq.heappop(hq)
        if cy == n-1 and cx == n-1:
            return cnt
        if visit[cy][cx] == -1:
            continue
        visit[cy][cx] = -1
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visit[ny][nx] != -1:
                if maze[ny][nx] == 1:
                    heapq.heappush(hq, [cnt, nx, ny])
                elif maze[ny][nx] == 0:
                    heapq.heappush(hq, [cnt+1, nx, ny])


print(bfs())