[다익스트라]백준 20182 골목 대장 호석 - 효율성 1

< Node 클래스 구현한 버전 >

package 다익스트라;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class boj_20182_골목대장호석효율성1 {
    private static int n, m, a, b, c, maxCost, cost[];
    private static List<Node>[] v;

    static class Node implements Comparable<Node>{
        int node;
        int cost;
        int shy;

        Node (int node, int cost){
            this.node = node;
            this.cost = cost;
        }

        Node (int node, int cost, int shy){
            this.node = node;
            this.cost = cost;
            this.shy = shy;
        }

        @Override
        public int compareTo(Node o) {
            return this.shy - o.shy;
        }
    }


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

        n = Integer.parseInt(tmp[0]);
        m = Integer.parseInt(tmp[1]);
        a = Integer.parseInt(tmp[2]);
        b = Integer.parseInt(tmp[3]);
        c = Integer.parseInt(tmp[4]);

        v = new List[n + 1];
        cost = new int[n + 1];
        // 배열 초기화
        for (int i = 0; i <= n ; i++) {
            v[i] = new ArrayList<Node>();
            cost[i] = 100000000;
        }

        // Input 값 넣기
        for (int i = 0; i < m; i++) {
            tmp = br.readLine().split(" ");
            int a = Integer.parseInt(tmp[0]);
            int b = Integer.parseInt(tmp[1]);
            int cost = Integer.parseInt(tmp[2]);
            v[a].add(new Node(b, cost));
            v[b].add(new Node(a, cost));
        }

        System.out.println(dijkstra());
    }

    private static int dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        pq.add(new Node(a, 0, 0));
        cost[a] = 0;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            int curNode = cur.node;

            if(curNode == b) return cost[curNode];

            int curCost = cur.cost;
            int curShy = cur.shy;


            if(cost[curNode] < curShy) continue;

            for (Node next: v[curNode]) {
                int nextNode = next.node;
                int nextCost = next.cost;

                // 누적 지불 금액 보다 소지한 금액이 더 크거나 같은지 && 수치심이 기존의 수치심 보다 낮은지
                if (curCost + nextCost <= c && cost[nextNode] > Math.max(cost[curNode], nextCost)) {
                    cost[nextNode] = Math.max(cost[curNode], nextCost);
                    pq.add(new Node(nextNode, nextCost + curCost, cost[nextNode]));
                }
            }

        }
        return -1;
    }
}

< 김포프님 방어적 프로그래밍 내용 적용 버전>

package 다익스트라;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class boj_20182_골목대장호석효율성1 {
    private static int n, m, a, b, c, maxCost, cost[];
    private static List<Node>[] v;

    static class Node implements Comparable<Node>{
        int node;
        int cost;
        int shy;

        Node (int node, int cost){
            this.node = node;
            this.cost = cost;
        }

        Node (int node, int cost, int shy){
            this.node = node;
            this.cost = cost;
            this.shy = shy;
        }

        @Override
        public int compareTo(Node o) {
            return this.shy - o.shy;
        }
    }


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

        n = Integer.parseInt(tmp[0]);
        m = Integer.parseInt(tmp[1]);
        a = Integer.parseInt(tmp[2]);
        b = Integer.parseInt(tmp[3]);
        c = Integer.parseInt(tmp[4]);

        v = new List[n + 1];
        cost = new int[n + 1];
        // 배열 초기화
        for (int i = 0; i <= n ; i++) {
            v[i] = new ArrayList<Node>();
            cost[i] = 100000000;
        }

        // Input 값 넣기
        for (int i = 0; i < m; i++) {
            tmp = br.readLine().split(" ");
            int a = Integer.parseInt(tmp[0]);
            int b = Integer.parseInt(tmp[1]);
            int cost = Integer.parseInt(tmp[2]);
            v[a].add(new Node(b, cost));
            v[b].add(new Node(a, cost));
        }

        System.out.println(dijkstra());
    }

    private static int dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        pq.add(new Node(a, 0, 0));
        cost[a] = 0;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            int curNode = cur.node;

            if(curNode == b) return cost[curNode];

            int curCost = cur.cost;
            int curShy = cur.shy;

            // 이미 방문했으면서 동시에 수치심이 이미 최소로 갱신되어 있을 경우
            if(cost[curNode] < curShy) continue;

            for (Node next: v[curNode]) {
                int nextNode = next.node;
                int nextCost = next.cost;

                // 누적 지불 금액 보다 소지한 금액이 더 크면 continue
                if(curCost + nextCost > c) continue;

                // 기존에 갱신된 수치심 보다 갱실될 수치심이 더 낮을 경우
                if(cost[nextNode] <= Math.max(cost[curNode], nextCost)) continue;

                    cost[nextNode] = Math.max(cost[curNode], nextCost);
                    pq.add(new Node(nextNode, nextCost + curCost, cost[nextNode]));
                }

        }
        return -1;
    }
}

< 클래스 구현 안한 버전 >

package 다익스트라;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class boj_20182_골목대장호석효율성1_클래스없이 {
    private static int n, m, a, b, c, maxCost, cost[];
    private static List[] v;


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

        n = Integer.parseInt(tmp[0]);
        m = Integer.parseInt(tmp[1]);
        a = Integer.parseInt(tmp[2]);
        b = Integer.parseInt(tmp[3]);
        c = Integer.parseInt(tmp[4]);

        v = new List[n + 1];
        cost = new int[n + 1];
        // 배열 초기화
        for (int i = 0; i <= n ; i++) {
            v[i] = new ArrayList<int[]>();
            cost[i] = 100000000;
        }

        // Input 값 넣기
        for (int i = 0; i < m; i++) {
            tmp = br.readLine().split(" ");
            int a = Integer.parseInt(tmp[0]);
            int b = Integer.parseInt(tmp[1]);
            int cost = Integer.parseInt(tmp[2]);
            v[a].add(new int[]{b, cost});
            v[b].add(new int[]{a, cost});
        }

        dijkstra();
        System.out.println(cost[b] == 100000000 ? -1 : cost[b]);
    }

    private static void dijkstra() {
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        pq.add(new int[]{a, 0, 0});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int curNode = cur[0];
            int accCost = cur[1];
            int maxCost = cur[2];

            for (int i = 0; i < v[curNode].size(); i++) {
                int nextNode[] = (int[]) v[curNode].get(i);
                int nextCur = nextNode[0];
                int nextCost = nextNode[1];

                int nextAccCost = accCost + nextCost;

                if(nextAccCost > c) continue;
                int nextMaxCost = Math.max(maxCost, nextCost);
                if(cost[nextCur] > nextMaxCost){
                    cost[nextCur] = nextMaxCost;
                    pq.add(new int[]{nextCur, nextAccCost, nextMaxCost});
                }

            }

        }

    }
}

해당 문제는 3일 동안 밤낮으로 고민한 끝에 풀었던 문제다.

 

결국 페어프로그래밍하던 친구가 C++로 짠 코드를 해석한 코드긴 한데 아이디어는 나왔지만 코딩을 못하고 있었던 내 자신을 돌아보게 해준 고마운 친구다.

 

접근 방향

1. 모든 경로를 다 둘러봐야한다.

2. 모든 경로를 둘러 보되 특정한 기준으로 프루닝이 필요하다.

3. 모든 경로를 둘러 보며 수치심의 최댓값이 최솟값이 되도록 구현되어야 한다.

 

1번 조건에 의해 완전탐색 방식을 선택해야 했다. 

2번 조건에 의해 다익스트라를 선택해야 했다.

3번 조건에 의해 수치심을 갱신할 저장공간이 필요했다.

 

그 결과 간선들을 둘러볼 때 일반 다익스트라는 간선의 누적합을 둘러보았지만, 해당 문제는 간선의 누적합 + 갱신된 수치심이 최솟값인지 확인을 한다.  

 

특정 노드 기준으로 모든 간선을 다 둘러본 뒤, 특정 값에 맞는 노드들만 최소힙에 넣는다.

최소힙의 객체가 없을 때까지 반복한다.

 

자꾸 헷갈렸던 부분은

// 이미 방문했으면서 동시에 수치심이 이미 최소로 갱신되어 있을 경우
if(cost[curNode] < curShy) continue;

 

해당 부분 때문에 반례가 생기지 않을지 였다.

if (curCost + nextCost <= c && cost[nextNode] > Math.max(cost[curNode], nextCost)) {
    cost[nextNode] = Math.max(cost[curNode], nextCost);
    pq.add(new Node(nextNode, nextCost + curCost, cost[nextNode]));
}

하지만 오해했던 부분이 일단 다음 노드 기준의 최댓값의 최솟값 배열과 현재 노드 기준의 최댓값과 지불해야할 비용의 최댓값을 비교하여 다음 노드보다 최댓값의 최솟값이 낮을 경우 최소힙에 넣는다는 것과 이미 방문했으면서 동시에 수치심이 이미 최소로 갱신되어 있을 경우가 동치라고 판단했던 부분이었다.

 

오랜만에 알고리즘을 풀다보니 손으로 끄적이거나 더 세밀하게 생각하기 보다 대충 패턴, 느낌으로 풀고자 해서 3일을 보낸 것 같은데 다익스트라라는 건 문제를 읽으면서 얼추 느꼈기 떄문에 비스무리한 문제를 많이 풀어봐야 할 것 같다.