[Python]4485-백준-녹색 옷 입은 애가 젤다지?

1. 문제 출처

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

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

2. 풀이

기본적인 데이크스트라 알고리즘을 사용하는 문제이다.

변형된 점은 인접한 노드를 구할 때 리스트나 메트릭스를 이용하는 것이 아닌 , 해당 좌표의 상하 좌우를 가지고 온다는 것이다.

# 데이크스트라 알고리즘을 위한 힙 모듈 불러오기
import heapq
# 입력
result = []
n = int(input())
while n!=0:
    #입력
    graph  = [[1] for _ in range(n)]
    for idx in range(n):
        graph[idx] = list(map(int, input().split()))
    # 잃어버리는 돈양을 저장하는 배열
    loss = [[float('inf')]*n for _ in range(n) ]
    # 상하좌우 이동
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]
    # 우선순위 큐
    q = []
    # 우선 순위 큐에  시작점인 0,0의 정보를 넣는다. 
    heapq.heappush(q,(graph[0][0] , [0,0]))
    # 0,0 에서 시작 하기 때문에 loss[0][0]을 graph[0][0]으로 한다.
    loss[0][0] = graph[0][0]
    # 우선순위 큐가 빌때까지 반복한다.
    while q:
        # 큐에서 제일 weight 가 작은 값을 뽑아온다.
        weight,(x,y) = heapq.heappop(q)
        # 만약 이미 가장 작은 값으로 된 값이면 그냥 넘긴다.
        if loss[x][y] < weight:
            continue
        # 인접한 4개의 노드중 갈 수 있는 노드 이면
        for idx in range(4):
            xx = x + dx[idx]
            yy = y + dy[idx]
            if (0<=xx<n) and (0<=yy<n):
                cost = weight + graph[xx][yy]
                # 해당 좌표로 가는 값이 최소값이라면
                if loss[xx][yy] > cost:
                    # 해당 값을 loss에 저장하고
                    # 우선 순위 큐에 해당 값을 추가한다. 
                    loss[xx][yy] = cost
                    heapq.heappush(q,(cost , [xx,yy]))
    result.append(loss[-1][-1])
    n = int(input())

for idx in range(len(result)):
    print(f"Problem {idx+1}: {result[idx]}")