백준 4485 녹색 옷 입은 애가 젤다지?

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

0,0 -> n-1,n-1 로 이동하는 최단거리 문제
최단거리 문제에서는 다익스트라를 쓸 수 있을까를 고민해봐야 한다.

이 문제를 dfs로 완전탐색 하기에는 넘 오래걸린다.
2차원 배열로 되어있지만, 그래프라고 생각하면 다익스트라를 접목시킬 수 있음이 생각난다.

기존 다익스트라에 노드의 위치 대신에 좌표를 넣어주면 된다.

1) 자바코드

import java.io.*;
import java.util.*;

public class Main {
    private static final int INF = 1000000000;
    private static int n;
    private static int[][] arr, dist;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};

    static class Node implements Comparable<Node>{
        int x,y,w;

        public Node(int x, int y, int w) {
            this.x = x;
            this.y = y;
            this.w = w;
        }

        @Override
        public int compareTo(Node o) {
            return this.w - o.w;
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int cnt = 1;
        while(true) {
            n = Integer.parseInt(br.readLine());
            if (n == 0) break;

            arr = new int[n+1][n+1];
            dist = new int[n+1][n+1];

            for (int i = 0; i < n; i++) {
                Arrays.fill(dist[i],Integer.MAX_VALUE);
            }
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine()," ");
                for (int j = 0; j < n; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            int res = dijkstra();
            sb.append("Problem " + cnt++ + ": " + res);
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    static int dijkstra(){
        dist[0][0] = arr[0][0];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0,0,arr[0][0]));

        while (!pq.isEmpty()) {
            Node poll = pq.poll();
            int x = poll.x;
            int y = poll.y;
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + x;
                int ny = dy[i] + y;
                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (dist[nx][ny] > dist[x][y] + arr[nx][ny]) {
                        dist[nx][ny] = dist[x][y] + arr[nx][ny];
                        pq.add(new Node(nx, ny, arr[nx][ny]));
                    }
                }
            }
        }
        return dist[n-1][n-1];
    }

}

2) 파이썬 코드

import math
import heapq
def dijkstra():
    q = [(arr[0][0],0,0)]
    dist[0][0] = arr[0][0]
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    while q:
        w,x,y = heapq.heappop(q)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if dist[nx][ny] > dist[x][y] + arr[nx][ny]:
                    dist[nx][ny] = dist[x][y] + arr[nx][ny]
                    heapq.heappush(q,(dist[nx][ny],nx,ny))
    return dist[n-1][n-1]


arr = []
dist = []
cnt = 0
while True:
    n = int(input())
    cnt += 1
    if n == 0:
        break
    arr = []
    for i in range(n):
        arr.append(list(map(int,input().split())))
    dist = [[math.inf]*n for i in range(n)]
    res = dijkstra()
    print(f"Problem {cnt}: {res}")