[Java/다익스트라] 백준 4485. 녹색 옷 입은 애가 젤다지?

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

🤔 Intuition

가중치가 있는 그래프 상에서, 가중치의 합이 최소가 되는 경로를 구하는 문제이므로 전형적인 다익스트라 문제이다.

 

다익스트라 기본 유형 연습용 문제로 보인다. 다익스트라 구현을 할 때 인접 행렬, 인접 리스트 두 가지 버전이 있으므로 두 가지로 풀어봤다.

🔎 Algorithm & Complexity

* @algorithm dijkstra
* @time1 O(E * logV) ; 인접리스트+우선순위큐 -> 264 ms
* @time2 O(V^2) ; 인접행렬 -> 1224 ms
* @memory O(V^2) -> 19908 KB, 27800 KB

👨🏻‍💻 Logic

이 문제는 간선의 개수가 노드당 최대 4개 뿐이며, N은 최대 125이므로 인접리스트를 이용한 풀이가 빠를 수 밖에 없다.

델타탐색(상하좌우) 기법을 이용하여 간선을 탐색하는 것 외에는 특별할 게 없는 다익스트라 문제이므로 시뮬레이션 서술은 생략한다.

 

인접리스트 풀이

public class BOJ_4485_녹색옷입은애가젤다지_우선순위큐 {
    private static int N, ny, nx, y, x;
    private static int[][] map;
    private static int[] start = {0, 0, 0};
    private static final int INF = (int) 1e9;
    private static final int Y = 0;
    private static final int X = 1;
    private static int[] dist;
    private static final int DIST = 2;
    private static Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[DIST]));
    private static int[] dy = {1, -1, 0, 0};
    private static int[] dx = {0, 0, 1, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int tc = 1;

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

            pq.clear();
            dist = new int[N * N];
            for (int i = 0; i < N * N; i++) {
                dist[i] = INF;
            }

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

            dist[0] = map[0][0];
            pq.add(start);

            while (!pq.isEmpty()) {
                int[] now = pq.poll();
                y = now[Y];
                x = now[X];

                for (int i = 0; i < 4; i++) {
                    ny = y + dy[i];
                    nx = x + dx[i];
                    if (inRange(ny, nx)) {
                        if (dist[ny * N + nx] > dist[y * N + x] + map[ny][nx]) {
                            dist[ny * N + nx] = dist[y * N + x] + map[ny][nx];
                            pq.add(new int[]{ny, nx, dist[ny * N + nx]});
                        }
                    }
                }
            }
            sb.append(String.format("Problem %d: %d\n", tc++, dist[N * N - 1]));
        }
        System.out.println(sb.toString());
    }

    private static boolean inRange(int y, int x) {
        return y >= 0 & y < N && x >= 0 && x < N;
    }
}

 

인접행렬 풀이

public class BOJ_4485_녹색옷입은애가젤다지_인접행렬 {
    private static int[][] map;
    private static boolean[] visited;
    private static int[] dist;
    private static int[] dy = {1, -1, 0, 0};
    private static int[] dx = {0, 0, 1, -1};
    private static int N, ans, totalNodes;
    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();
        StringTokenizer st;
        // 상하좌우로는 반드시 갈수있고,
        // 간 곳은 갈 필요 없고
        long TC = 0;

        while (true) {
            N = Integer.parseInt(br.readLine());
            TC++;
            if (N == 0) {
                break;
            }
            totalNodes = N * N;
            map = new int[N][N];
            visited = new boolean[totalNodes];
            dist = new int[totalNodes];

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

            for (int i = 0; i < totalNodes; i++) {
                dist[i] = (int) 1e9;
            }

            dist[0] = map[0][0]; // start node

            top:
            for (int i = 0; i < totalNodes; i++) {
                // 아직 방문하지 않은 노드 중에서 최단거리 노드 찾기
                int minIdx = -1;
                for (int j = 0; j < totalNodes; j++) {
                    if (visited[j]) {
                        continue;
                    }
                    if (minIdx == -1 || dist[j] < dist[minIdx]) {
                        minIdx = j; // 최단거리 노드 찾기
                    }
                }
                visited[minIdx] = true;

                // 최단거리 노드가 나왔으니 그 노드의 인접 노드를 탐색하며 출발지로부터 거리 갱신
                int y = minIdx / N;
                int x = minIdx % N;
                for (int j = 0; j < 4; j++) {
                    int ny = y + dy[j];
                    int nx = x + dx[j];
                    if (inRange(ny, nx)) {
                        int w = map[ny][nx];
                        dist[ny * N + nx] = Math.min(dist[ny * N + nx], dist[minIdx] + w);
                        if (ny == N - 1 && nx == N - 1) { // 도착 지점이라면
                            ans = dist[ny * N + nx];
                            break top;
                        }
                    }
                }
            }
            sb.append(String.format("Problem %d: %d\n", TC, ans));
        }

        br.close();
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static boolean inRange(int y, int x) {
        return y >= 0 & y < N && x >= 0 && x < N;
    }
}