[BOJ/Java] 4485. 녹색 옷 입은 애가 젤다지?

[BOJ/Java] 4485. 녹색 옷 입은 애가 젤다지?

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

---

문제 해석

이 문제는 다익스트라 알고리즘을 이용하여 최소 비용 경로를 찾는 문제이다. 각 칸에는 비용이 존재하고, 이 비용을 최소화하면서 오른쪽 아래 구석으로 이동해야 한다. 이 문제는 전형적인 그리드 기반의 최단 경로 문제로, 각 점에서 상하좌우 네 방향으로 이동할 수 있다.

풀이 과정

입력받은 그리드 map에 대하여 다익스트라 알고리즘을 적용하여 해결한다. 우선적으로 weight 배열을 사용하여 각 칸까지의 최소 비용을 저장한다. 시작점인 (0,0)의 비용은 그 위치의 map값으로 초기화된다.

다익스트라 알고리즘의 핵심은 우선순위 큐를 사용하는 것으로, 현재 가장 낮은 비용의 위치를 먼저 처리하여 경로를 확장한다. 이 문제에서는 Point 클래스를 정의하여 x, y 위치와 해당 위치까지의 누적 비용을 관리한다. 각 점에서 이웃한 점들을 탐색하고, 새로운 비용이 기존 weight 배열에 저장된 비용보다 작다면 갱신하고 큐에 추가한다.

이러한 과정을 반복하면서 목표 위치인 (N-1, N-1)에 도달할 때 그 때의 비용이 최소 비용이 되며, 이를 결과로 반환한다.

코드

package edu.ssafy.im.BOJ.Gold.G4.No4485;

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static int N;
    private static int[][] map;
    private static final int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int T = 1;
        while ((N = Integer.parseInt(br.readLine())) != 0) {
            map = new int[N][N];
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            sb.append("Problem ").append(T).append(":").append(" ").append(Dijkstra()).append("\n");
            T++;
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int Dijkstra() {
        int[][] weight = new int[N][N];
        for(int[] w : weight) Arrays.fill(w, Integer.MAX_VALUE);  // 최소 비용을 저장할 배열 초기화
        weight[0][0] = map[0][0];  // 시작 위치의 비용 초기화

        Queue<Point> pq = new PriorityQueue<>();  // 우선순위 큐 사용
        pq.offer(new Point(0, 0, weight[0][0]));  // 시작 위치 큐에 추가

        while(!pq.isEmpty()) {
            Point p = pq.poll();

            if (p.x == N-1 && p.y == N-1) return p.w;  // 목적지 도달 시 금액 반환

            for (int[] d: direction) {  // 사방 탐색
                int nx = p.x + d[0];
                int ny = p.y + d[1];

                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

                if (p.w + map[nx][ny] < weight[nx][ny]) {  // 최소 금액 갱신
                    weight[nx][ny] = p.w + map[nx][ny];
                    pq.add(new Point(nx, ny, weight[nx][ny]));  // 갱신된 위치 큐에 추가
                }
            }
        }
        return -1;
    }

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

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

        @Override
        public int compareTo(Point p) {
            return this.w - p.w;  // 우선순위 큐를 위한 비용 비교
        }
    }
}

시간 복잡도 분석

이 문제의 시간 복잡도는 다익스트라 알고리즘의 시간 복잡도인 𝑂(𝑉^2)에서 𝑉는 그리드 내의 셀 수, 즉 𝑁×𝑁이다. 이를 우선순위 큐를 사용하여 최적화할 경우 𝑂((𝑁^2)log⁡(𝑁^2))가 될 수 있다.

느낀점

이 문제를 통해 다익스트라 알고리즘이 그리드 기반 경로 탐색 문제에 얼마나 효과적으로 적용될 수 있는지 확인할 수 있었다. 특히, 우선순위 큐를 활용한 점이 이 문제의 해결에 중요한 역할을 했다. 이와 같은 접근 방식은 다른 그래프 탐색 문제에도 유용하게 적용될 수 있다는 것을 느꼈다.