백준 | 2211번. 네트워크 복구 - 다익스트라 문풀 (java)

⬛ 백준 2211번. 네트워크 복구 - 다익스트라 문풀 (java)

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

문제

N(1 ≤ N ≤ 1,000)개의 컴퓨터로 구성된 네트워크가 있다. 이들 중 몇 개의 컴퓨터들은 서로 네트워크 연결이 되어 있어 서로 다른 두 컴퓨터 간 통신이 가능하도록 되어 있다. 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다.

각 컴퓨터들과 회선은 그 성능이 차이가 날 수 있다. 따라서 각각의 직접 연결되어 있는 회선을 이용해서 통신을 하는데 걸리는 시간이 서로 다를 수 있다. 심지어는 직접 연결되어 있는 회선이 오히려 더 느려서, 다른 컴퓨터를 통해서 통신을 하는 것이 더 유리할 수도 있다. 직접 연결되어 있는 회선을 사용할 경우에는 그 회선을 이용해서 통신을 하는 데 드는 시간만큼이 들게 된다. 여러 개의 회선을 거치는 경우에는 각 회선을 이용해서 통신을 하는 데 드는 시간의 합만큼의 시간이 걸리게 된다.

어느 날, 해커가 네트워크에 침입하였다. 네트워크의 관리자는 우선 모든 회선과 컴퓨터를 차단한 후, 해커의 공격을 막을 수 있었다. 관리자는 컴퓨터에 보안 시스템을 설치하려 하였는데, 버전 문제로 보안 시스템을 한 대의 슈퍼컴퓨터에만 설치할 수 있었다. 한 컴퓨터가 공격을 받게 되면, 네트워크를 통해 슈퍼컴퓨터에 이 사실이 전달이 되고, 그러면 슈퍼컴퓨터에서는 네트워크를 이용해서 보안 패킷을 전송하는 방식을 사용하기로 하였다. 준비를 마친 뒤, 관리자는 다시 네트워크를 복구하기로 하였다. 이때, 다음의 조건들이 만족되어야 한다.

1. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다. 물론, 그렇다면 아무 회선도 복구하지 않으면 되겠지만, 이럴 경우 네트워크의 사용에 지장이 생기게 된다. 따라서 네트워크를 복구한 후에 서로 다른 두 컴퓨터 간에 통신이 가능하도록 복구해야 한다.
2. 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

원래의 네트워크에 대한 정보가 주어졌을 때, 위의 조건을 만족하면서 네트워크를 복구하는 방법을 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다. 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다. 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다.

출력

첫째 줄에 복구할 회선의 개수 K를 출력한다. 다음 K개의 줄에는 복구한 회선을 나타내는 두 정수 A, B를 출력한다. 이는 A번 컴퓨터와 B번 컴퓨터를 연결하던 회선을 복구한다는 의미이다. 출력은 임의의 순서대로 하며, 답이 여러 개 존재하는 경우에는 아무 것이나 하나만 출력하면 된다.

---

💚 문제 접근 방식

전형적인 다익스트라 문제이다.

그런데 경로를 저장하는 부분이 좀 헷갈렸다.

1) 슈퍼컴퓨터 1번과 최소 경로로 연결하는 간선 정보를 구하는 문제이므로 다익스트라를 활용한다.

 

2) 일반 다익스트라 알고리즘을 활용하여 distance[]로 다른 정점에 대한 최단 경로를 구하되, 이 과정에서 갱신할 때마다 routine[]배열에 서로 갱신한 두 정점에 대한 정보를 세팅한다.

 

3) 만약 routine[i] = 0 인 정점이 있다는 것은 (갱신 안되어 초기값 갖는 것이므로) 다른 노드와 연결되지 않은 컴퓨터라 ‘복구 컴퓨터’에 포함되지 않는다. 그래서 무시한다.

 

4) 그외의 경우에는 모두 해당 idx와 routine[idx] 값을 차례로 출력하면 된다.

 

💚 제출 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

class Edge implements Comparable<Edge>{
    int e, val;
    Edge(int e, int val){
        this.e =e;
        this.val = val;
    }
    @Override
    public int compareTo(Edge o) {
        return this.val- o.val;//가중치 오름차순
    }
}

public class Main {
    static List<List<Edge>> graph;
    static int N, M;
    static int[] distance;
    static int[] routine;
    //간선 연결 정보를 현재 정점-다음 정점 순으로 담아야 되나 ?

    //dijkstra
    static void dijkstra(int st){
        PriorityQueue<Edge> pQ = new PriorityQueue<>();
        distance[st] = 0;
        pQ.offer(new Edge(st, 0));
        
        while(!pQ.isEmpty()) {
            Edge cur = pQ.poll();
            if (cur.val > distance[cur.e])
                continue;
            for (Edge nx : graph.get(cur.e)) {
                if (distance[nx.e] > distance[cur.e] + nx.val) {
                    distance[nx.e] = distance[cur.e] + nx.val;
                    pQ.offer(new Edge(nx.e, distance[nx.e]));
                    routine[nx.e] = cur.e;
                }
            }
        }
    }

    //실행 메인
    public static void main(String[] args) {
        Scanner kb=  new Scanner(System.in);
        N = kb.nextInt();
        M = kb.nextInt();

        distance = new int[N+1];
        Arrays.fill(distance, Integer.MAX_VALUE);

        graph = new ArrayList<>();
        for(int i=0; i<=N; i++){
            graph.add(new ArrayList<>());
        }

        //데이터 입력
        for(int i=0; i<M; i++){
            int a = kb.nextInt();
            int b = kb.nextInt();
            int v = kb.nextInt();
            //양바향 간선
            graph.get(a).add(new Edge(b, v));
            graph.get(b).add(new Edge(a, v));
        }
        
        routine = new int[N+1];
        
        dijkstra(1);
        
        StringBuilder sb = new StringBuilder();
        
        int cnt = 0;
        for(int i=2; i<=N; i++) {
        	if(routine[i]==0) continue;
        	cnt++;
        	sb.append(i+ " " + routine[i] + "\\n");
        }
        
        System.out.println(cnt);
        System.out.println(sb.toString());
    }
}

 

---

💚 회고

다익스트로 매번 최단 경로를 구하는 것에 그치지 않고,  갱신된 경로(정점)을 중복 없이 만들 수 있는지가 핵심인 문제였다. routine[인덱스]=값에 서로 연결된 정점을 담긴 할 건데 1번 정점은 슈퍼 컴퓨터이므로 제외하고, 값이 0인 경우는 연결이 안된 정점이라 제외한다면 StringBuilder로 각 정점들의 값을 담아 출력하면 됐다. 비슷한 아이디어를 잘 참고하여 다음에 비슷한 문제를 헤매지 않도록 하자.