백준 4485(녹색 옷 입은 애가 젤다지?) - 다익스트라알고리즘, 힙구조, 최단거리- python

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

예제 풀이

일단 첨에는 DFS로 이용해서 풀었지만 아니나 다를까,, 바로 시간초과..⭐️

그래서 생각한건 다익스트라 알고리즘으로 최단 경로 알고리즘이었다..

예제 하나를 이용해서 다익스트라 알고리즘을 풀이하면 다음 사진과 같다고 생각하면 이해하기 쉽다. 

만약 다익스트라 알고리즘이 먼가,, 이것부터라면 밑에 링크로 들어가는것을 추천한다 (나름 이코테 책보면서 정리해둔 다익스트라알고리즘이다. )

[이코테] CHAPTER 09 최단 경로 알고리즘 - 다익스트라 최단 경로 알고리즘

 

---

문제 핵심🥸

① 우선순위 큐 사용(heapq) : heaq 모듈 사용 -> 비용이 적은 노드부터 꺼냄
② 상하좌우 탐색 사용 : move = [(-1,0),(1,0),(0,-1),(0,1)] 배열 선언하고 상하좌우 이동
③ visited 이차원 배열에 최단 경로 갱신
④ 큐가 비어지면 탐색이 종료

 

---

코드 작성

💻Python(파이썬)

import sys
import heapq

# 무한대를 나타내는 값 설정
INF = int(1e9)

input = sys.stdin.readline

# 다익스트라 알고리즘 함수 정의
def dijkstra(graph, n):
    # 각 노드의 최소 비용을 기록할 2차원 리스트 초기화 (무한대로 초기화)
    visited = [[INF] * n for _ in range(n)]
    visited[0][0] = graph[0][0]  # 시작 지점의 비용 설정

    # 우선순위 큐 사용 (현재 비용, x 좌표, y 좌표)
    q = []
    heapq.heappush(q, (graph[0][0], 0, 0))  # 시작점 추가

    # 상하좌우 이동을 위한 배열
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # 큐가 비어 있지 않을 때까지 반복
    while q:
        # 가장 짧은 거리를 가진 노드 정보 꺼내기
        cost, x, y = heapq.heappop(q)

        # 인접한 노드 탐색
        for dx, dy in move:
            new_x, new_y = x + dx, y + dy

            # 그래프 범위를 벗어나지 않는지 확인
            if 0 <= new_x < n and 0 <= new_y < n:
                # 현재 노드를 통해 인접 노드로 이동하는 비용 계산
                new_cost = cost + graph[new_x][new_y]

                # 계산된 비용이 기록된 비용보다 작으면 갱신
                if new_cost < visited[new_x][new_y]:
                    visited[new_x][new_y] = new_cost
                    heapq.heappush(q, (new_cost, new_x, new_y))  # 큐에 추가

    # 목적지 (n-1, n-1)의 최소 비용 반환
    return visited[n-1][n-1]

# 입력 처리 및 다익스트라 알고리즘 실행
n = int(input().strip())
count = 1  # 문제 번호
while n:
    # 그래프 입력
    graph = [list(map(int, input().strip().split())) for _ in range(n)]

    # 다익스트라 알고리즘 실행 및 결과 출력
    result = dijkstra(graph, n)
    print("Problem %d: %d" % (count, result))

    count += 1  # 문제 번호 증가
    n = int(input().strip())  # 다음 그래프의 크기 입력