BOJ - 네트워크 복구 2211번 (JAVA)

❓ 문제 - 백준 네트워크 복구 2211번 - JAVA 풀이법

 

출처

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

2211번: 네트워크 복구

 

 

📝 문제해결법

1. 문제

• N개로 구성된 컴퓨터에서 1번(슈퍼컴퓨터)와 다른 컴퓨터들을 최소 경로의 비용으로 연결시켜야 한다.
• 이때, 복구한 회선의 갯수와 복구한 회선의 수를 나타내는 두 정수 A, B를 출력한다.

 

2. 해결 방법

• 문제를 봤을 때 N의 범위가 우선 (1 <= N <= 1000)이고, 하나의 노드(1번->슈퍼컴퓨터)에서 최소 경로로 연결하는 간선들에 대한 정보를 구하는 문제이므로 다익스트라 알고리즘을 활용한다.
• 일반 다익스트라 알고리즘처럼 1번 노드로 부터 다익스트라를 시작해서 distance에 1번 노드로 부터의 다른 노드의 최소 간선 비용, connect에는 i번과 연결된(복구된) 다른 노드의 회선 정보를 저장한다.
• 만약 connect[i]가 0 이라면 다른 노드와 연결되지 않은 컴퓨터이므로 복구 컴퓨터에 들어가지 않는다.

 

 

3. 느낀점

• 일반적으로 다익스트라 알고리즘을 알고 있다면 쉽게 접근할 수 있는 문제 같았다

 

💻 소스코드 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_2211 {
    public static int n, m;
    public static int[] distance, connect;
    public static int INF = (int)1e9;
    public static class Edge implements Comparable<Edge>{
        int a;
        int dis;
        public Edge(int a, int dis){
            this.a = a;
            this.dis = dis;
        }

        @Override
        public int compareTo(Edge o) {
            return this.dis - o.dis;
        }
    }

    public static ArrayList<Edge>[] list;
    public static int cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        list = new ArrayList[n+1];
        distance = new int[n+1];
        connect = new int[n+1];

        for(int i=0;i<n+1;i++){
            list[i] = new ArrayList<Edge>();
        }

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int dis = Integer.parseInt(st.nextToken());

            list[a].add(new Edge(b, dis));
            list[b].add(new Edge(a, dis));
        }

        Arrays.fill(distance, INF);
        dijkstra();

        for(int i=2;i<=n;i++){
            if(connect[i] == 0) continue;
            cnt++;
            sb.append(i+ " " + connect[i]+"\n");
        }
        System.out.println(cnt);
        System.out.println(sb.toString());
    }

    public static void dijkstra(){
        distance[1] = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(1, 0));
        while (!pq.isEmpty()){
            Edge edge = pq.poll();

            if(edge.dis > distance[edge.a]) continue;

            for(Edge e:list[edge.a]){
                if(distance[e.a] > e.dis + edge.dis){
                    distance[e.a]  = e.dis + edge.dis;
                    connect[e.a] = edge.a;
                    pq.add(new Edge(e.a, distance[e.a]));
                }
            }
        }
    }
}