항해 99 코테 스터디 5기 3일차 + [백준] 네트워크 복구 java 풀이

1. 문제 설명 📌

문제 링크

문제를 보며, 찾아낸 조건은 다음 3가지 였다.

• 1️⃣ 최소 개수의 회선을 복구하라

• 2️⃣ 모든 서로 다른 2 대의 컴퓨터가 교신이 가능해야 한다.

• 3️⃣ 슈퍼 컴퓨터에서 다른 컴퓨터로의 통신 최소 비용은 복구 이전과 같아야 한다.

  문제를 풀며 느낀 점은,
  3️⃣ 때문에 1️⃣은 있으나 마나 한 조건이 되었다. 3️⃣을 만족시키려면 다익스트라를 활용해서, 최단 경로를 찾아야 하고, 그 최단 경로에 사용된 회선보다 개수를 더 줄일 수 없기 때문이다. (줄이면, 어떤 컴퓨터에는 슈퍼컴퓨터가 도달하지 못한다.) 2️⃣ 또한 다익스트라를 활용하면, 최소 슈퍼 컴퓨터를 매개로 모두 교신할 수 있기에 따로 구현해야 하는 조건이 아니다. 따라서 다익스트라를 하며 거쳐가 경로를 기억하는 문제이다.

2. 구현 방법 🗃️

KEY WORD: DIJKSTRA

• 0️⃣ 인접 리스트 구현 용 클래스인 Node와 다익스트라용 클래스인 Dist를 나눠서 구현한다.
  • 이때 DIST에는 거쳐온 간선 정보를 저장하는 HashSet<Edge> edge를 구현해 놓는다.
  • HashSet<Edge> edge는 HashMap의 동등성을 위하여 hashCode와 equals를 override하여 구현해 놓는다.
  • 최단거리 배열도 Dist를 자료형으로 구현한다.
• 1️⃣ 다익스트라를 진행한다. 최단 거리 배열의 dist(도착지까지의 최단거리)가 갱신될 때마다, 최단 거리 배열의 Edge Set도 갱신한다. (만약 dist[B] > dist[A] + A ➜ B의 간선 비용 으로 갱신되었다면, dist[B].edge는 원래 값은 비우고, dist[A].edge + new Edge(A, B)로 채운다.)
• 2️⃣다익스트라가 끝난 뒤에는 최단 거리 배열을 돌며, 모든 Edge를 전체 HashSet에 넣는다. (중복 제거 + 모든 간선을 한 곳에 저장)
• 3️⃣ 전체 HashSet의 Size와 각 간선을 출력한다.

(1) 시간복잡도 분석 🕓

정점의 수를 V, 간선의 수를 E라고 할 때,
기본 다익스트라 시간 복잡도 $O(V \log E)$

• 첫 반복에는 최대 0개의 간선을 삭제하고, 최대 1 개의 간선을 삽입한다.
• 두 번째 반복에는 최대 1개의 간선을 삭제하고, 최대 2개의 간선을 삽입한다.
• ...
• V번째 반복에는 최대 $V-1$개의 간선을 삭제하고, $V$개의 간선을 삽입한다.

총 $O(V^{2})$

즉 $O(V \log E) + O(V^{2})$ 로 시간복잡도는 $O(V^{2})$ 다.

내 풀이가 통과한 이유는 아마, 정점의 개수가 최대 1000개라서 인 것 같다.

3. 코드 소개 🔎

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


public class Main {
    static int N,M;
    static ArrayList<Node> [] lists;
    static Dist [] dists;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        lists = new ArrayList[N + 1];

        for (int i = 1; i < N + 1; i++) {
            lists[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start   = Integer.parseInt(st.nextToken());
            int end     = Integer.parseInt(st.nextToken());
            int weight  = Integer.parseInt(st.nextToken());

            lists[start].add(new Node(end, weight));
            lists[end].add(new Node(start, weight));
        }
        dijkstra();
        HashSet<Edge> sum = new HashSet<>();
        StringBuilder ans = new StringBuilder();

        for (int i = 1; i < N + 1; i++) {
            sum.addAll(dists[i].routes);
        }
        ans.append(sum.size()).append("\n");
        for (Edge now : sum){
            ans.append(now.start).append(" ").append(now.end).append("\n");
        }
        System.out.println(ans.toString());
    }

    public static void dijkstra () {
        dists = new Dist[N + 1];
        for (int i = 1; i < N + 1; i++) {
            dists[i] = new Dist(i);
        }
        dists[1].dist = 0;

        PriorityQueue<Dist> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.dist));
        pq.add(new Dist(1,0));

        while(!pq.isEmpty()){
            Dist now = pq.poll();

            if(now.dist != dists[now.idx].dist) continue;

            for (int i = 0; i < lists[now.idx].size(); i++) {
                Node next = lists[now.idx].get(i);
                if(dists[next.idx].dist > dists[now.idx].dist + next.w) {
                    dists[next.idx].dist = dists[now.idx].dist + next.w;
                    dists[next.idx].routes.clear();
                    dists[next.idx].routes.addAll(dists[now.idx].routes);
                    dists[next.idx].routes.add(new Edge(now.idx, next.idx));
                    pq.add(new Dist(next.idx, dists[next.idx].dist, dists[next.idx].routes));
                }
            }
        }
    }
}

class Dist {
    int idx;
    int dist;
    HashSet<Edge> routes;

    public Dist (int i) {
        this.idx = i;
        this.dist = Integer.MAX_VALUE;
        routes = new HashSet<>();
    }

    public Dist (int i, int dist){
        this.idx = i;
        this.dist = dist;
    }

    public Dist (int i, int dist, HashSet<Edge> prev){
        this.idx = i;
        this.dist = dist;
        routes = new HashSet<>();
        routes.addAll(prev);
    }

    public String toString() {
        return "[" + idx + ", " + dist + ", " + routes + "]";
    }
}


class Node {
    int idx;
    int w;

    public Node (int idx, int w) {
        this.idx = idx;
        this.w = w;
    }
}

class Edge {
    int start;
    int end;

    public Edge (int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int hashCode(){
        return this.start + this.end;
    }

    @Override
    public boolean equals(Object obj) {
        if(obj.getClass() != this.getClass()) return false;
        Edge o = (Edge) obj;
        return o.start == this.start && o.end == this.end;
    }
}

4. 배운 것들 🎯

첫 풀이는 만약 '후에 계산한 최단 거리 가중치가 같으면, 간선을 적게 쓴 녀석으로 dist를 갱신한다'는 의미의 코드를 작성했다. 하지만, 해당 코드는 무의미하게 계산 시간만 잡아먹는 코드이다. 왜냐하면, 무슨 경로를 쓰든 사용된 전체 간선의 개수에 어짜피 1개만 더해지기 때문이다.


해당 예시에서는 B,C가 먼저 방문 될 것이고, 다음은 A를 방문할 차례다. 우선순위 큐 구현에 따라서 출발지에서 바로 A로 가는 3이 먼저 뜨겠지만, 우리는 1 ➜ 1 ➜ 1이 먼저 큐에서 나오고 뒤에 간선 1개 짜리 3이 큐에서 나온다고 해보자.

                if(dists[next.idx].dist == dists[now.idx].dist + next.w &&
                    dists[next.idx].routes.size() > dists[now.idx].routes.size() + 1) {
                    dists[next.idx].routes.clear();
                    dists[next.idx].routes.addAll(dists[now.idx].routes);
                    dists[next.idx].routes.add(new Edge(now.idx, next.idx));
                }

그려면 내가 적은 해당 코드에 따라, (출발지,B)➜ (B,C) ➜ (C,A)은 폐기 되고 (출발지,A)로 dist[A]는 갱신될 것이다. 근데 나중에 합치면, 두 경우의 수 모두 간선은 3개만 사용한다.
[A, B], [B, C]. [C, A] 이든, [A,B], [B,C], [A,C] 이든 말이다.