[Python] 백준 2665번 미로만들기

문제

2665번: 미로만들기

입력

• 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

출력

• 첫 줄에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력한다.

입력 예제

8
11100110
11010010
10011010
11101100
01000111
00110001
11011000
11000111

출력 예제

2

문제 풀이

• 방문경로 체크하면서 최단거리 탐색
• 최단거리 탐색하면서 검은색이라면(그래프의 값이 0이면) 흰색으로 바꿔준다 
• 목적좌표에 도달했다면 흰색으로 바꾼 횟수 리턴해서 출력

코드

import heapq
import sys
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
input = sys.stdin.readline
n = int(input())
INF = int(1e9)
graph = []
visited = [[0] * n for _ in range(n)]
for _ in range(n):
    graph.append(list(map(int,input().rstrip())))


def dijkstra(y, x):
    q = []
    heapq.heappush(q, (0, y, x))
    visited[y][x] = 1

    while q:
        dist, y, x = heapq.heappop(q)
        if y == n - 1 and x == n - 1:
            return dist
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < n and 0 <= nx < n and not visited[ny][nx]:
                visited[ny][nx] = 1
                if graph[ny][nx] == 0:
                    heapq.heappush(q,(dist + 1, ny, nx))
                else:
                    heapq.heappush(q,(dist, ny, nx))


print(dijkstra(0, 0))