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

특별한건 없었고 다익스트라를 사용하면 바로 해결할 수 있는 문제이다.

📜 문제 바로 가기 : 녹색 옷 입은 애가 젤다지?

제출코드

파이썬

import sys
input = sys.stdin.readline

import heapq

def dij():
    hq = []
    heapq.heappush(hq, (arr[0][0], 0, 0)) # cost, i, j
    
    cost_arr = [[999999] * N for _ in range(N)]
    cost_arr[0][0] = arr[0][0]

    while hq:
        nowCost, ni, nj = heapq.heappop(hq)

        if cost_arr[ni][nj] < nowCost:
            continue

        for di, dj in delta:
            i = ni + di
            j = nj + dj
            if isRange(i, j) and cost_arr[i][j] > nowCost + arr[i][j]:
                cost_arr[i][j] = nowCost + arr[i][j]
                heapq.heappush(hq, (nowCost + arr[i][j], i, j))

    return cost_arr[N-1][N-1]


def isRange(i, j):
    if 0 <= i < N and 0 <= j < N:
        return True
    return False



delta = [(1,0), (-1,0), (0,1), (0,-1)]

round = 0
while 1:
    N = int(input())
    if N == 0:
        break
    
    round += 1
    arr = [list(map(int, input().split())) for _ in range(N)]

    a = dij()
    print(f"Problem {round}: {a}")

자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int[][] delta = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}};
    static int[][] arr;
    static int N;
    static Main mySolve = new Main();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        int round = 0;
        while (true) {
            N = Integer.parseInt(br.readLine());
            if (N == 0) {
                break;
            }

            round += 1;

            arr = new int[N][N];
            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 ans = mySolve.dij();
            System.out.println("Problem " + round + ": " + ans);
        }
    }

    public int dij() {
        PriorityQueue<Node> hq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.cost - o2.cost;
            }
        });

        hq.add(new Node(0, 0, arr[0][0]));
        int[][] cost_arr = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cost_arr[i][j] = Integer.MAX_VALUE;
            }
        }
        cost_arr[0][0] = arr[0][0];

        while (hq.size() != 0) {
            Node now = hq.poll();

            if (cost_arr[now.i][now.j] < now.cost) {
                continue;
            }

            for (int k = 0; k < 4; k++) {
                int i = now.i + delta[k][0];
                int j = now.j + delta[k][1];
                if (isRange(i, j) == true && cost_arr[i][j] > arr[i][j] + now.cost) {
                    Node newNode = new Node(i, j, arr[i][j] + now.cost);
                    cost_arr[i][j] = newNode.cost;
                    hq.add(newNode);
                }
            }
        }

        return cost_arr[N-1][N-1];
    }

    public static boolean isRange(int i, int j) {
        if ( 0 <= i && i < N && 0 <= j && j < N) {
            return true;
        }
        return false;
    }

    class Node {
        int cost;
        int i;
        int j;

        public Node(int i, int j, int dis) {
            this.i = i;
            this.j = j;
            this.cost = dis;
        }
    }
}

---

접근방법

다익스트라 끝!