[백준] 2665 파이썬

문제

---

• 백준 2665 (골드 4)

백준 2665

n X n 모양의 방이 있을 때, 검은 방을 거치지 않고 흰 방만을 거쳐서 탈출하는 문제였다.
여기서 문제의 조건은 탈출할 수 없는 경우, 최소의 수의 검은 방을 흰 방으로 바꿔서 탈출하라는 것이였다.
방의 색이 입력으로 주어지면 색을 바꿔야할 방의 최소의 수를 출력한다.

내 코드

---

20분정도 어떻게 구현해야할지 고민해보았는데 마땅히 아이디어가 떠오르지 않아서 힌트를 봤다.
다익스트라 알고리즘을 사용해야 한다는 사실을 알고는 바로 어떻게 구현해야할지가 보였다.
각 칸까지 이동하는데 색을 바꿔야하는 방의 최소의 수를 담을 테이블을 하나 생성한다.
각 간을 탐색하면서 테이블을 계속 최솟값으로 갱신해주면 마지막 칸에서의 색을 바꿔야하는 방의 최소의 수를 구할 수 있다.

import sys
import heapq
input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n)]
for i in range(n):
    arr = list(map(str,input().strip()))
    for x in arr:
        graph[i].append(int(x))
table = [[sys.maxsize] * n for _ in range(n)]
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

def dijkstra(stx, sty):
    q = []
    heapq.heappush(q, (0, stx, sty))
    table[sty][stx] = 0
    while q:
        w, x, y = heapq.heappop(q)
        if table[y][x] < w:
            continue
        for k in range(4):
            nx = dx[k] + x
            ny = dy[k] + y
            if 0 <= nx < n and 0 <= ny < n:
                if graph[ny][nx] == 1:
                    if table[y][x] < table[ny][nx]:
                        table[ny][nx] = table[y][x]
                        heapq.heappush(q, (table[y][x], nx, ny))
                else:
                    if table[y][x] + 1 < table[ny][nx]:
                        table[ny][nx] = table[y][x] + 1
                        heapq.heappush(q, (table[y][x] + 1, nx, ny))

dijkstra(0, 0)

print(table[n-1][n-1])

다익스트라 알고리즘이 아직 덜 숙련된 거 같아 자연스럽게 떠오를 수 있도록 더 많은 문제를 풀어봐야 할 것 같다.