[BOJ] 4485. 녹색 옷 입은 애가 젤다지?

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

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

 

 

1. 해결방법

"""
1. 아이디어
- 출발 점에서 목적 점 까지 가는데 사용하는 최송 비용 : 다익스트라
- 간선, 인접리스트 저장
- 거리 비용 배열 저장
- 힙이 빌때까지 다음 반복
    - 힙의 최솟값을 꺼냄
    - 상하좌우 이동하면서 최솟값을 갱신
    - 해당 노드와 인접한 노드를 인접리스트에서 가져와서 힙에 저장
"""

 

 

2. 정답코드

import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
count = 0

while True:
    N = int(input())
    if N == 0:
        break

    graph = [list(map(int, input().split())) for _ in range(N)]

    count += 1
    start = 0
    dist = [[INF] * (N) for _ in range(N)]
    dist[start][start] = 0
    heap = [[graph[start][start], start, start]]

    while heap:
        cost, ey, ex = heapq.heappop(heap)

        # 종료 지점
        if ey == N - 1 and ex == N - 1:
            print(f'Problem {count}: {cost}')

        for i in range(4):
            ny, nx = ey + dy[i], ex + dx[i]

            if 0 <= ny < N and 0 <= nx < N:
                ncost = cost + graph[ny][nx]

                if dist[ny][nx] > ncost:
                    dist[ny][nx] = ncost
                    heapq.heappush(heap, [dist[ny][nx], ny, nx])

 

개인적으로 정말 좋은 문제였다.
잊고 있었던 그래프 이론을 복습할 수 있는 문제였으며, 다익스트라 기본 코드를 살짝 변형해서 풀 수 있는 좋은 문제이다.

문제를 잘 읽어봐야한다.
그래프 위치에서 떠나면 떠나기 전의 루피를 소모하는 형태이다. 그래서 디폴트 값을 잘 정해주는게 중요하며 dy, dx를 이용해서 그래프 이동하는 로직도 중요하다. 나머지는 다익스트라이다.