[Python] BOJ / 2665번 / 미로만들기

2665번: 미로만들기

---

📝 풀이

• n x n 바둑판 모양으로 총 n^2개의 방이 있을 때, 윗줄 맨 왼쪽 시작방에서부터 아랫줄 맨 오른쪽 끝방으로 이동하는데 필요한 방의 색을 바꾸는 횟수를 최소로 하는 경우를 구하는 프로그램
  • 흰방은 1, 검은방은 0으로 나타내며 검은방은 지나갈 수 없는 방이다.
• 다익스트라 알고리즘으로 구현할 수 있으며 최소 힙을 방의 색을 바꾼 횟수를 기준으로 정렬한다.

---

💻 소스코드

import sys
import heapq

input = sys.stdin.readline
dy = (1, -1, 0, 0)
dx = (0, 0, 1, -1)

def dijkstra():
    heap = []
    heapq.heappush(heap, (0, 0, 0))
    visited[0][0] = True

    while heap:
        cnt, y, x = heapq.heappop(heap)

        if y == n - 1 and x == n - 1:
            return cnt
        
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if not 0 <= ny < n or not 0 <= nx < n or visited[ny][nx]:
                continue

            visited[ny][nx] = True
            if room[ny][nx] == 1:
                heapq.heappush(heap, (cnt, ny, nx))
            else:
                heapq.heappush(heap, (cnt + 1, ny, nx))

n = int(input())
room = [list(map(int, input().strip())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

print(dijkstra())