자바(백준) 1922 네트워크 연결

오답 노트 & 새로 알게 된 점

해당 문제는 MST알고리즘 기본 문제이다. 

왜 이 문제가 MST 문제인지를 알아야할 것 같다. 

보면 문제에서 모든 컴퓨터가 연결이 되어 있어야 한다. 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 라는 말이 MST를 이용하라는 것 같다.

최소 비용으로 연결하기 위해서는 간선을 최소화시켜야하고, 그 중에서 가중치를 제일 낮은 것들을 선택해야한다. 또한, 컴퓨터가 모두 연결이 되어 있어야한다는 조건도 말이다.

 

그래서 크루스칼 알고리즘을 사용하여 findSet, unionSet 자료구조를 직접 구현하고, 출발과 끝, 가중치를 저장하고 있는 ArrayList를 가중치에 따라 오름차순으로 정렬하고, parent 배열을 이용하여 구현했다.

 

여기서 유심히 보아야 할 점은 unionSet으로 연결을 할 때, 

if( ++cnt = N - 1) 이다.

왜냐하면 간선의 개수가 정점 개수의 N-1을 만족하기 때문에, 위 조건을 쓰게 되면 더욱 더 빨리 끝낼 수 있다. 

그리고 연결을 할 때, findSet을 이용하여 연결하려는 두 정점이 같은 대표자(같은 집합)인지 확인해야한다.

if(findSet(u) != findSet(v))

 

---

 

코드

package Graph;
 
import java.io.*;
import java.util.*;
 
public class BOJ1922 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
 
    static int parent[];
    static int N, M;
    static ArrayList<ComPoint> al = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = atoi(br.readLine());
        M = atoi(br.readLine());
        parent = new int[N + 1];
        Arrays.fill(parent, -1);
 
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s1 = atoi(st.nextToken());
            int s2 = atoi(st.nextToken());
            int wei = atoi(st.nextToken());
 
            al.add(new ComPoint(s1, s2, wei));
        }
 
        Collections.sort(al, (o1, o2) ->  {
            return o1.wei - o2.wei;
        });
        
        int rel = 0;
        int cnt = 0;
        for (int i = 0; i < al.size(); i++) {
            if(findSet(al.get(i).st) != findSet(al.get(i).ed)){
                rel += al.get(i).wei;
                unionSet(al.get(i).st, al.get(i).ed);
                if(++cnt == N - 1) break;
            }
        }
 
        System.out.println(rel);
    }
 
    static int findSet(int v) {
        if(parent[v] < 0) return v;
        return findSet(parent[v]);
    }
 
    static void unionSet(int u, int v) {
        u = findSet(u);
        v = findSet(v);
        if(u == v) return;
        parent[u] += parent[v];
        parent[v] = u;
    }
 
    static class ComPoint{
        int st, ed, wei;
 
        public ComPoint(int st, int ed, int wei) {
            this.st = st;
            this.ed = ed;
            this.wei = wei;
        }
    }
}