[SWExpertAcademy]1249번 [S/W 문제해결 응용] 4일차 - 보급로 - Java

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD 

SW Expert Academy

 

 

풀이

문제를 읽어보면 딱 다익스트라 쓰면 풀 수 있겠구나 하고 감이 온다.

출발지랑 도착지가 정해져있고 최소 비용을 구하는 거니까!

도로를 복구하는 시간 말고 최단 거리 같은 조건은 없으니까 별 다를게 없는 그냥 다익스트라 문제이다.

 

https://seokmimmmmmmmm.tistory.com/84

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

이 문제랑 걍 똑같다고 보면 된다.

 

다익스트라 문제 풀 때 중요한건 최솟값을 찾는 알고리즘이다 보니, answerMap(정답 배열)은 최대값(Integer.MAX_VALUE)으로 채워줘야 한다! (0, 0)에서 시작하는 경우 (0, 0)은 처음 값을 넣어주고 나머지는 최대값으로 채워줘야 함.

그리고 그냥 큐를 사용해도 문제는 풀리지만, 우선 순위 큐를 사용하면 값이 작은 애들부터 처리하기 때문에 최소값 보다 큰 애들을 큐에 넣는 수고를 덜 할 수 있다. 시간이 절약된다는 거임!

if (answerMap[nr][nc] <= map[nr][nc] + answerMap[r][c]) {
    continue;
}

answerMap[nr][nc] = map[nr][nc] + answerMap[r][c];
pq.offer(new Node(nr, nc, map[nr][nc]));

solution() 안의 while문 안의 해당 조건문에서 걸러질 것이기 때문!!

경우의 수가 많아지면 많아질 수록 더 효율적일 것이다!

이런 유형을 많이 풀어봐야겠다 ㅎㅎ

 

** PQ는 희소그래프일 때 효과적임 간선이 개ㅐㅐㅐ 많으면 최적화가 안됨! 어떤 문제든 PQ를 쓴다고 최적화가 되진 않음!!!

 

코드

// 1249 - [S/W 문제해결 응용] 4일차 - 보급로

package d4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Num1249_보급로 {
    static int N;
    static int[][] map;
    static int[][] answerMap;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};

    private static class Node implements Comparable<Node> {
        int r;
        int c;
        int weight;

        public Node(int r, int c, int weight) {
            this.r = r;
            this.c = c;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return this.weight = o.weight;
        }
    }

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

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine());

            map = new int[N][N];
            answerMap = new int[N][N];

            for (int i = 0; i < N; i++) {
                String str = br.readLine();
                for (int j = 0; j < N; j++) {
                    map[i][j] = str.charAt(j) - '0';
                }
            }

            for (int i = 0; i < N; i++) {
                Arrays.fill(answerMap[i], Integer.MAX_VALUE);
            }
            answerMap[0][0] = 0;

            solution();

            System.out.println("#" + t + " " + answerMap[N - 1][N - 1]);
        }
    }

    private static void solution() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(0, 0, 0));

        while (!pq.isEmpty()) {
//            // 테스트
//            for (int t = 0; t < N; t++) {
//                System.out.println(Arrays.toString(answerMap[t]));
//            }
//            System.out.println();
//
//            // 테스트
//            for (int t = 0; t < N; t++) {
//                System.out.println(Arrays.toString(map[t]));
//            }
//            System.out.println();

            Node temp = pq.poll();

            int r = temp.r;
            int c = temp.c;

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
                    continue;
                }

                if (answerMap[nr][nc] <= map[nr][nc] + answerMap[r][c]) {
                    continue;
                }

                answerMap[nr][nc] = map[nr][nc] + answerMap[r][c];
                pq.offer(new Node(nr, nc, map[nr][nc]));
            }
        }
    }
}