[PS] 백준2211 : 네트워크 복구(Java)

문제

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

2211번: 네트워크 복구

---

풀이

Dijkstra를 활용한 풀이

접근법

조건

- 첫번째 컴퓨터는 슈퍼컴퓨터로써 반드시 복구해야합니다.

- 슈퍼 컴퓨터로부터 나머지 N-1개의 컴퓨터까지 최단 경로로 통신이 가능해야합니다.

- 양방향 그래프

 

풀이

1. 간단한 데이크스트라를 통해 슈퍼 컴퓨터를 시작노드로 나머지 노드까지의 최단경로를 우선순위 큐를 통해 탐색.
2. 탐색하는 과정에서 방문체크를 같이 진행.
3. 이전 정점을 알아야 하기 때문에 prev라는 배열을 통해 이전 정점을 같이 기록.
4. 새로운 정점을 탐색할 때 마다 이전정점과 현재정점의 간선을 연결.

정리해보자면,

해당 문제는 주어진 간선들에 대한 정보를 통해 최단 경로로 슈퍼 컴퓨터와 모든 컴퓨터가 통신할 수 있도록하는 간선을 찾는 문제입니다.

 

얼핏 보기엔 MST로 헷갈릴 수 있는 문제지만 문제 내용 중 2번 조건때문에 데이크스트라를 활용하여 풀이를 해야합니다.

또한 새로운 정점을 탐색할 때 마다 이전 정점과의 간선을 연결하는 것으로 문제의 조건들을 만족할 수 있다는 것을 알고 있어야합니다. ( == 우선순위 큐 데이크스트라의 특성에 의해 )

 

연결되는 정점의 정보 또한 출력을 해야하므로 prev라는 추가적인 배열을 사용함으로써 약간의 기믹을 활용합니다.

또한 약간의 최적화를 위해 새로운 정점이 탐색될 때 마다 cnt라는 변수를 통해 연결된 정점 개수를 기록하며 모든 정점이 연결되었을 때 종료시킴으로써 시간복잡도 최적화를 진행할 수 있습니다.

 

---

소스코드

import java.io.*;
import java.util.*;

//BOJ_2211 네트워크 복구
public class Main {
    static class Node {
        int v;
        int w;
        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
    static int N, M, res;
    static List<List<Node>> list;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        list = new ArrayList<>();
        for(int i=0; i<=N; i++) list.add(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());
            list.get(start).add(new Node(end, weight));
            list.get(end).add(new Node(start, weight));
        }

        Dijkstra(1);
        System.out.println(res);
        System.out.print(sb);
    }

    private static void Dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.w - o2.w;
            }
        });
        pq.offer(new Node(start, 0));
        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        int[] prev = new int[N+1];
        boolean[] vv = new boolean[N+1];
        vv[start] = true;
        int cnt = 1;

        while(!pq.isEmpty()) {
            Node cur = pq.poll();
            if(!vv[cur.v] && prev[cur.v] != 0) {
                vv[cur.v] = true;
                sb.append(prev[cur.v] + " " + cur.v).append("\\n");
                res++;
                cnt++; //정점 연결 개수
                if(cnt == N+1) return; //모든 정점과 연결이 되었다면 종료
            }

            for(Node n : list.get(cur.v)) {
                int totalWeight = n.w + cur.w;
                if(totalWeight < dist[n.v]) {
                    pq.offer(new Node(n.v, totalWeight));
                    dist[n.v] = totalWeight;
                    prev[n.v] = cur.v;
                }
            }
        }
    }
}

 

---

반례

<https://www.acmicpc.net/board/view/70830>

 

---

정리

첫번째 접근에서 슈퍼 컴퓨터를 제외한 나머지 정점들로부터 슈퍼 컴퓨터까지의 최단경로를 전부 탐색하여 연결 간선을 찾는 것으로 풀이를 했는데 4% 시간초과를 받았습니다..

오랜만에 다시 알고리즘 문제를 풀어서 그런가 적응하기에는 참 좋았던 문제였고, 접근법이 좀처럼 떠오르기 쉽지 않은 문제였던 것 같습니다.