[Python] 백준 4485 녹색 옷 입은 애가 젤다지? | 다익스트라

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://www.acmicpc.net/problem/4485

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

 

 

문제 해결 포인트

- 다익스트라를 이용하여 각 위치별 (0, 0)에서 최소 비용을 계산

- dr, dc : 각 위치에서 아래, 위, 오른쪽, 왼쪽 위치를 방문 하기 위한 방향키

- graph : 각 위치 방문을 위해 필요한 비용

- distance : 각 위치에서 (0, 0)까지 가기위한 최소 비용, 초기는 무한수

 

 

작성 코드

import heapq
INF = int(1e9)
dr = [1, -1, 0, 0]  # down, up, right, left
dc = [0, 0, 1, -1]

test = 1
while True:
    n = int(input())
    if n == 0:
        break

    distance = [[INF]*(n+1) for _ in range(n+1)]
    graph = [[] for _ in range(n)]
    for i in range(n):
        graph[i] = list(map(int, input().split()))

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

        while q:
            dist, row, col = heapq.heappop(q)
            if distance[row][col] < dist:
                continue
            for d in range(4):
                r = row + dr[d]
                c = col + dc[d]
                if -1 < r < n and -1 < c < n and distance[r][c] > graph[r][c] + dist:
                    distance[r][c] = dist + graph[r][c]
                    heapq.heappush(q, (distance[r][c], r, c))

    dijkstra(0, 0)
    print("Problem {}: {}".format(test, distance[n-1][n-1]))
    test += 1

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

궁금한 점이 있다면 댓글 달아주세요!