[백준] 4485번 녹색 옷 입은 애가 젤다지?(파이썬)

문제

4485번: 녹색 옷 입은 애가 젤다지?

다익스트라 알고리즘구현 틀

Python으로 다익스트라(dijkstra) 알고리즘 구현하기

이 블로그를 보고 다익스트라를 만드는 법을 배워서 문제를 푸는데 활용해 보았다.

코드

# 우선순위 큐 구현
import sys, heapq
input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1,]


def coin():
    # 시작값은 0
    move[0][0] = 0
    queue = []
    # 시작 노드부터 탐색을 시작하기 위해
    heapq.heappush(queue, [cave[0][0], 0, 0])

    # queue안에 남아있는 노드가 없으면 끝 
    while queue:
        have_coin, x, y = heapq.heappop(queue)
        if x == n - 1 and y == n - 1:
            print(f'Problem {cnt}: {move[x][y]}')
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 해당 코인보다 덜 먹는 경로라면 저장
            if 0 <= nx < n and 0 <= ny < n and move[nx][ny] > have_coin + cave[nx][ny]:
                move[nx][ny] =  have_coin + cave[nx][ny]
                heapq.heappush(queue, [move[nx][ny], nx, ny])

cnt = 0
while True:
    cnt += 1
    n = int(input())
    if n == 0:
        break
    cave = [list(map(int, input().split())) for _ in range(n)]
    move = [[int(10e9)] * n for _ in range(n)]

    coin()

해설

다익스트라(최단경로) 문제이다. 다익스트라는 처음 구현해보는터라 위 블로그를 참고해서 코드를 구현해 보았다.

큰 틀을 설명하자면,

1. 경로를 저장하는 move를 만든다. 여기서 안에 있는 숫자를 최소로 비교하면서 들어갈 거기 때문에 무한으로 설정해주었다.
2. 경로를 지나갈 함수를 만든다. 경로를 하나하나 꺼내가면서 값을 저장할 거기때문에 BFS방식을 가져온다.(heapq)
3. queue 안에 [코인, 경로(x, y)]를 넣어준다.
4. queue 안이 빌 때까지 반복해준다.
5. queue의 종료 구문을 설정해준다. (x, y가 n-1일때)
6. 아닐때는 위아래좌우로 가서 지금 경로보다 더 적은 코인을 먹었을때를 저장해주고 queue에 넣어준다.