[BOJ_4485] 녹색 옷 입은 애가 젤다지?

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

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

🏗️ 설계

dijkstra 알고리즘을 이용하여, 최소가 되는 거리들을 PriorityQueue에서 꺼낸 후 최소 거리를 갱신해 나가는 방식으로 풀이하였습니다.

📋 코드

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

public class BOJ_4485 {

    static final int MAX_DIST = 1_000_000_000;
    static int[][] board;
    static int[][] dist;
    static int size;
    static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    static class Pair<F, S> {
        F first;
        S second;

        public Pair(F first, S second) {
            this.first = first;
            this.second = second;
        }
    }

    public static void init() {
        board = new int[size][size];
        dist = new int[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                dist[i][j] = MAX_DIST;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int problemNum = 0;
        while (true) {
            size = Integer.parseInt(br.readLine());
            if (size == 0) {
                System.out.println(sb.toString());
                return;
            }
            sb.append("Problem ").append(++problemNum).append(": ");

            init();

            for (int i = 0; i < size; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < size; j++) {
                    board[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            dijkstra();

            sb.append(dist[size - 1][size - 1]).append("\n");
        }
    }

    private static void dijkstra() {
        Queue<Pair<Integer, Pair<Integer, Integer>>> pq = new PriorityQueue<>((o1, o2) -> o1.first - o2.first);
        pq.add(new Pair(board[0][0], new Pair(0, 0)));

        dist[0][0] = board[0][0];

        while (!pq.isEmpty()) {
            Pair<Integer, Pair<Integer, Integer>> tmp = pq.poll();
            int curRow = tmp.second.first;
            int curCol = tmp.second.second;
            for (int i = 0; i < 4; i++) {
                int nextRow = curRow + dir[i][0];
                int nextCol = curCol + dir[i][1];
                if (check(nextRow, nextCol)) {
                    int nextCost = board[nextRow][nextCol];
                    if (dist[nextRow][nextCol] > dist[curRow][curCol] + nextCost) {
                        dist[nextRow][nextCol] = dist[curRow][curCol] + nextCost;
                        pq.add(new Pair(dist[nextRow][nextCol], new Pair(nextRow, nextCol)));
                    }
                }
            }
        }
    }

    private static boolean check(int row, int col) {
        return row >= 0 && row < size && col >= 0 && col < size;
    }
}

👎 어려웠던 점

• 인접리스트 형태로 된 그래프에서 풀이하던 것과 비슷한 형식이지만 2차원 배열에서 dijkstra 알고리즘을 적용하는 과정이 어려웠습니다.

⏰ 사용한 메모리 / 시간

• Memory : 20580KB
• Time : 256ms