[백준4485] / 녹색 옷 입은 애가 젤다지? - 다익스트라/그래프탐색

 

백준4485

 

푼 날짜 : 2024.11.19

푼 문제 : [4485] / 녹색 옷 입은 애가 젤다지?

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근방식 :

N이 0일 때까지 반복하므로 while True에서 N 값에 따라 break를 넣어주었다.

 

현재위치가 x, y 일때 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 모두 탐색 가능하므로 4방향 탐색을 진행한다.

이때 값이 더 작은 경우 업데이트 해주고 아니라면 넘어간다.

 

 

코드 :

import sys
import heapq

input = sys.stdin.readline
INF = float("INF")

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

def dijkstra(N, graph):
    heap = [(graph[0][0], 0, 0)]
    dist = [[INF for _ in range(N)] for _ in range(N)]
    dist[0][0] = graph[0][0]

    while heap:
        now_cost, now_i, now_j = heapq.heappop(heap)
        if dist[now_i][now_j] < now_cost: continue
		
        # 4방향 탐색
        for i in range(4):
            ny, nx = now_i+dy[i], now_j+dx[i]

            if 0<=ny<N and 0<=nx<N:
                all_cost = now_cost + graph[ny][nx]
                
                # 비용이 더 작을 때 
                if dist[ny][nx] > all_cost:
                    dist[ny][nx] = all_cost
                    heapq.heappush(heap, (all_cost, ny, nx))

    # 도착점에서의 최소 비용 출력
    return dist[N-1][N-1]

# 단계 출력을 위한 변수
idx = 1
while True:
    N = int(input())
    if N == 0: break # N이 0이라면 종료

    graph = []
    for _ in range(N):
        lst = list(map(int, input().split()))
        graph.append(lst)
        
    ans = dijkstra(N, graph)
    print(f"Problem {idx}:", ans)
    idx +=1

 

 

젤다는 안해봤는데 재밌으려나..~