백준 2211번 네트워크 복구 (JAVA)

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

2211번: 네트워크 복구

 

저는 해당 문제를 다익스트라를 통해서 문제를 해결하였습니다.

저는 최소 개수의 회선만을 복구해야하고, 통신하는데 걸리는 시간이 원래 네트워크에서 통신하는 시간보다 커지면 안된다는 부분에서 생각을 하였습니다. 계속 생각보니 다익스트라 알고리즘을 적용하면 둘의 조건이 모두 해결되었습니다.

결국 n-1개의 회선을 연결해야하며, 다익스트라는 시작점에서 각각의 점에 최단 거리를 구하는 것이기 때문에 통신 시간이 커질 수 없었습니다.

저는 m의 범위가 주어지지 않았고, 공통된 연결된 회선 (1과 2이 연결된 회선이 가중치가 다른 2개의 회선)의 존재 여부가 문제에 주어지지 않아 저는 배열로 표현하는 것이 조금 더 좋아 보여 배열을 통해 표현하였습니다.

시간 복잡도 : O(n^2)

 

package BOJ.MST;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_2211 {
    private static final int INF = 987654321;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        int[][] map = new int[n+1][n+1];
        for(int i = 0 ; i <= n ; i++){
            Arrays.fill(map[i],INF);
        }
        for(int i = 0 ; i < m ; i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = stoi.apply(st.nextToken());
            int b = stoi.apply(st.nextToken());
            int c = stoi.apply(st.nextToken());
            map[a][b] = Math.min(c,map[a][b]);
            map[b][a] = Math.min(c,map[b][a]);
        }
        List<int[]> result = dij(map,1,n);
        System.out.println(result.size());
        for(int[] edge : result){
            System.out.println(edge[0]+" "+edge[1]);
        }
    }

    private static List<int[]> dij(int[][] map, int start,int n) {
        List<int[]> result = new LinkedList<>();
        int[] distance = new int[n+1];
        int[] path = new int[n+1];
        boolean[] visited = new boolean[n+1];
        Arrays.fill(distance,INF);
        distance[start] = 0;
        for(int i = 0 ; i < n ; i++){
            int minIndex = 0;
            int minValue = INF;
            for(int j = 1; j <= n ; j++){
                if(!visited[j] && minValue > distance[j]){
                    minValue = distance[j];
                    minIndex = j;
                }
            }
            if(minValue == INF){
                break;
            }
            visited[minIndex] = true;
            if(minIndex != start){
                result.add(new int[] {path[minIndex],minIndex});
            }
            for(int j = 1; j <= n ; j++){
                if(!visited[j] && distance[j] > minValue + map[minIndex][j]){
                    distance[j] = minValue + map[minIndex][j];
                    path[j] = minIndex;
                }
            }
        }
        return result;
    }
}