[백준] 1922번 : 네트워크 연결 - 자바(Java)

Problem 🔒

문제

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

 

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.

출력

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

예제 입력 1

6
9
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
3 5 11
4 5 3
4 6 8
5 6 8

예제 출력 1

23

---

Approach 1 ⭕ - 크루스칼 알고리즘

1. 입력 및 초기화
   • 입력 개수가 10만개가 넘어가므로 BufferedReader를 사용했다.
   • 컴퓨터의 수와 간선의 수를 Integer.parseInt(br.readLine()) 으로 받았다.
     • br.read() 로 받으면 자료형이 int이지만, 한 문자를 읽어서 정수로 반환하기 때문에, 입력 값이 제대로 해석되지 않는다.
   • 크루스칼 알고리즘에서는 간선의 비용을 기준으로 정렬이 필요하기 때문에 리스트 형태로 저장했다.
   • 리스트에는 {비용, 정점1, 정점2} 형태의 배열로 간선을 추가하였다.
   • 유니온파인드 연산을 하기 위해 (컴퓨터의 수+1)만큼 배열을 생성하고, -1로 초기화한다.
2. 간선 선택
   • 반복문을 간선의 수만큼 진행하며, 선택한 간선 수가 N-1개이면 종료한다.
   • 리스트에서 간선 하나를 꺼내어, check( ) 메서드로 두 컴퓨터가 이미 같은 그룹인지 검사를 진행한다.
   • 같은 그룹이면 다음 반복문으로 넘어간다.
   • 같은 그룹이 아니면 해당 간선을 선택하고, 비용과 선택한 간선 수를 갱신한다.
3. 같은 그룹인지 확인(check(int u, int v) 메서드)
   • u번 컴퓨터의 루트노드와 v번 컴퓨터의 루트노드를 find(int x)를 사용해 찾는다.
   • 루트 노드가 서로 같으면 이미 같은 그룹이므로 false를 리턴한다. (싸이클 생성 여부)
   • u번 컴퓨터가 속한 트리를 a, v번 컴퓨터가 속한 트리를 b라고 할 때 a 트리의 높이가 더 높은 트리가 되도록 고정한다. (union by rank 최적화)
   • v번 컴퓨터의 루트노드를 u번 컴퓨터의 루트노드 자식으로 변경한다.
   • 같은 그룹으로 묶었으므로 true를 리턴한다.
4. 루트노드 찾기(find(int x) 메서드)
   • 재귀를 활용해, 부모노드를 타고 올라가면서 루트노드를 찾는다.
   • x의 부모 값이 음수이면, 루트노드임을 의미하므로 루트노드를 리턴한다.
   • 부모노드를 타고 올라가면서 만난 노드들의 부모를 루트노드로 변경한다(경로 압축 최적화)

Approach 2 ⭕ - 프림 알고리즘

프림 알고리즘은 임의의 정점에서 매번 비용이 가장 적은 간선을 선택해 나가는 방식이다.

1. 입력
   • 그룹으로 묶였는지는 방문배열로 확인하기 위해 방문배열을 생성한다.
     • 프림 알고리즘은 방문하지 않은 정점 중 비용이 가장 작은 정점을 선택한다.
     • 이미 선택한 정점에 대해 다시 간선을 추가하지 않기 때문에 싸이클이 생길 수 없다.
   • 이중리스트에 간선들을 {인접한 노드, 비용} 배열 형태로 저장한다.
2. 프림 알고리즘(prim() 메서드)
   • 우선순위 큐를 활용하여 비용이 적은 간선을 기준으로 정렬한다.
   • 큐에 임의의 정점1과 비용0을 추가한다.
   • 큐가 빌 때까지 반복문을 진행하고, 선택한 간선의 수가 N개이면 반복문을 종료한다.
     • N-1개가 아니라 N개인 이유는 처음에 시작하는 정점에서 간선을 선택하지 않았는데 선택한 간선의 수를 하나 증가시켜서이다.
   • 큐에서 비용이 가장 작은 간선을 꺼내어 해당 정점에 방문했으면 무시한다. (방문했다는 의미는 이미 그룹화되었다는 뜻이다.)
   • 방문하지 않았으면, 방문처리하고 선택한 간선의 수를 증가시킨다.
   • 방문처리한 정점과 인접한 간선들 중 방문하지 않은 정점들을 큐에 추가한다.

(크루스칼 + 우선순위 큐)는 다른 분들의 풀이를 보고, 크루스칼 알고리즘에서 간선을 저장할때 ArrayList에 저장하는 것을 우선순위 큐로만 변경한 것이다. 충분히 생각해볼 수 있었던 아이디어인데 놓쳐서 아쉬웠다. 

---

Solution 💡

크루스칼 알고리즘

public class 네트워크연결 {
    static int N, M, tree[];
    static ArrayList<int[]> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        tree = new int[N+1];
        Arrays.fill(tree, -1);
        StringTokenizer st;
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.add(new int[]{c,u,v});
        }
        Collections.sort(list, (a,b)->(a[0]-b[0])); // 비용 오름차순 정렬
        int ans = 0; // 출력할 최소비용
        int edge = 0; // 선택한 간선 수 : N-1개이면 반복문 종료
        // 간선 수만큼 반복
        for(int i=0; i<M; i++){
            int[] current = list.get(i);
            int curCost = current[0];
            int curU = current[1];
            int curV = current[2];
            if(!check(curU, curV)) continue;
            ans += curCost;
            edge++;
            if(edge==N-1) break;
        }
        System.out.println(ans);
    }

    public static boolean check(int u, int v){
        int a = find(u);
        int b = find(v);
        if(a==b) return false; // 이미 같은 그룹일 때
        if(tree[b] < tree[a]){
            int tmp = a;
            a = b;
            b = tmp;
        }
        if(tree[a]==tree[b]) tree[a]--;
        tree[b] = a;
        return true; // 같은 그룹으로 묶었으면 true 반환
    }

    public static int find(int x){
        if(tree[x]<0) return x;
        return tree[x] = find(tree[x]); // 경로압축
    }
}

프림 알고리즘

public class 네트워크연결 {
    static int N, M;
    static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        visit = new boolean[N+1];
        for(int i=0; i<N+1; i++){list.add(new ArrayList<>());}
        StringTokenizer st;
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.get(u).add(new int[]{v,c});
            list.get(v).add(new int[]{u,c});
        }
        int ans = prim(); // 출력할 최소비용
        System.out.println(ans);
    }
    public static int prim(){
        int cost = 0, edge = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->(a[1]-b[1]));
        q.add(new int[]{1,0}); // 임의의 한 정점부터 시작

        while (!q.isEmpty()){
            int[] current = q.poll();
            int curNode = current[0];
            int curCost = current[1];
            if(visit[curNode]) continue; // 방문했으면 다음 반복문으로
            visit[curNode] = true; // 방문처리
            edge++;
            cost += curCost;

            for(int[] next : list.get(curNode)){
                int nextNode = next[0];
                int nextCost = next[1];
                if(!visit[nextNode]){
                    q.add(new int[]{nextNode, nextCost});
                }
            }
            if(edge==N) break;
        }
        return cost;
    }
}