BOJ - 4485

백준 문제 링크
녹색 옷 입은 애가 젤다지?

❓접근법

1. 다익스트라 알고리즘을 활용했다.
2. 초기값 distance = [[INF] * N for _ in range(N)],
   상,하,좌,우로 움직일 수 있으므로 dx, dy를 지정하고
   x, y = 0, 0에서 시작한다.
3. 다익스트라 함수 내에서 q를 만들어 heapq.heappush로
   graph[x][y], x, y를 q에 넣어주고,
   distance[x][y] = graph[x][y]로 지정한다.
4. 4 방향으로 움직인 후 범위를 벗어나지 않으면
   cost = (현재 루피 + 다음 방향 루피(graph[nx][ny])로 지정하고

• if cost < distance[nx][ny]:
  • distance[nx][ny] = cost
  • heapq.heappush(q, (cost, nx, ny)) 해준다.

5. 다익스트라 함수를 x, y에 대해 실행시키고
   가장 마지막 값을 문제의 출력 형식에 맞게 출력하면 끝!

👌🏻코드

import heapq

cnt = 0
INF = int(1e9)
while True:
    N = int(input())
    cnt += 1
    
    if N == 0:
        break
        
    distance = [[INF] * N for _ in range(N)]
    
    graph = []
    for _ in range(N):
        graph.append(list(map(int, input().split())))
    
    x, y = 0, 0
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    def dijkstra(x,y):
        q = []
        
        heapq.heappush(q, (graph[x][y], x, y))
        distance[x][y] = graph[x][y]
        
        while q:
            dist, x, y = heapq.heappop(q)
            
            if distance[x][y] < dist:
                continue
                
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                
                if nx < 0 or nx >= N or ny < 0 or ny >= N:
                    continue
                    
                cost = dist + graph[nx][ny]
                if cost < distance[nx][ny]:
                    distance[nx][ny] = cost
                    heapq.heappush(q, (cost, nx, ny))
                                
    dijkstra(x,y)
    answer = distance[N-1][N-1]
    print(f"Problem {cnt}: {answer}")