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

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

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

문제설명

N x N 크기의 격자에서 출발점(0,0)에서 도착점(N-1,N-1)으로 가는 최소 거리를 찾는다.

4개의 방향(상하좌우)으로만 이동할 수 있으며,  각 셀은 특정 비용이 있다. 이 비용은 그 셀을 통과할 때 발생한다.

접근방식

O(N^2 log N) 시간복잡도

 

다익스트라 알고리즘의 시간 복잡도

• 우선순위 큐에 추가 및 삭제:
  • 각 셀에 대해 최대 O(log(V))의 시간이 걸리며, V는 노드의 수이다.
  • 격자의 크기가 N x N이므로 V = N^2이다.

E는 간선의 수로, 격자에서는 각 노드가 최대 4개의 간선을 가질 수 있으므로 E는 O(N^2)이다.

전체 시간 복잡도는 O(N^2 log(N^2)) = O(N^2 log N)이다.

.

문제 조건 분석 과정

 

그래프의 최단 경로를 찾는 데 다익스트라 알고리즘을 사용한다.

1. 우선순위 큐(Priority Queue): 최소 비용을 기준으로 셀을 선택한다.
2. 비용 배열(dijk): 각 셀에 도달하는 최소 비용을 저장한다. 초기값은 무한대로 설정한다.
3. 시작점 설정: (0, 0) 위치에서 시작 비용을 해당 위치의 값으로 설정한다.
4. 이동: 현재 셀에서 상하좌우로 이동 가능한 모든 셀을 확인하고, 더 낮은 비용으로 해당 셀에 도달할 수 있다면 비용을 업데이트하고 큐에 추가한다.
5. 종료 조건: 도착점(N-1, N-1)에 도달하면 그 비용을 반환한다.

전체코드

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

public class Main {
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static int INF = 10000000;

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

        int cnt = 1;

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

            sb.append("Problem ").append(cnt++).append(": ");
            int[][] 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());
            }
            sb.append(dijkstra(arr, N)).append('\n');
        }
        System.out.println(sb);
        br.close();
    }

    static int dijkstra(int[][] arr, int n) {
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);

        int[][] dijk = new int[n][n];
        for(int i=0; i<n; i++)
            Arrays.fill(dijk[i], INF);

        q.offer(new int[] {0, 0, arr[0][0]});
        dijk[0][0] = arr[0][0];

        while(!q.isEmpty()) {
            int temp[] = q.poll();
            int row = temp[0];
            int col = temp[1];

            for(int i=0; i<4; i++) {
                int nextRow = row + dx[i];
                int nextCol = col + dy[i];

                if(nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n
                        && dijk[nextRow][nextCol] > dijk[row][col] + arr[nextRow][nextCol]) {
                    dijk[nextRow][nextCol] = dijk[row][col] + arr[nextRow][nextCol];
                    q.offer(new int[] {nextRow, nextCol, dijk[nextRow][nextCol]});
                }
            }
        }
        return dijk[n - 1][n - 1];
    }
}