[BOJ] 1922 네트워크 연결 - JAVA

1. 문제

1922번: 네트워크 연결

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

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

---

2. 풀이

MST, 그 중에서도 크루스칼 풀이를 이용했다.

Main

parent에 노드 부모번호를 저장했다. 초반에는 자기자신이 부모이므로 i값으로 초기화를 해주었다.

힙을 이용해서 value가 가장 작은 것부터 뽑을 수 있도록 했다. 따로 클래스를 만들지는 않고 int 배열을 사용했다.

 

1.  힙이 빌 때까지 반복한다.

2.  첫번째, 두번째 수의 부모를 구한다.

3.  부모가 같다면 서클이 생기는 것이므로 합치지 않고 continue한다.

4.  총 비용 cost에 value를 추가하고 2를 서로 합친다.

static int[] parent;
public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   int N = Integer.parseInt(in.readLine());
   int M = Integer.parseInt(in.readLine());

   parent = new int[N+1];
   for(int i=1;i<=N;i++) parent[i] = i;

   PriorityQueue<int[]> queue = new PriorityQueue<>((o1,o2)->o1[2]-o2[2]);//오름차순
   StringTokenizer st;
   for(int i=0;i<M;i++){
      st = new StringTokenizer(in.readLine());
      queue.offer(new int[]{Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())});
   }

   int[] now;
   int cost = 0;
   while(!queue.isEmpty()){
      now = queue.poll();
      int a = find(now[0]);
      int b = find(now[1]);
      if(a==b) continue;
      cost += now[2];
      union(a,b);
   }

   System.out.println(cost);

}

 

union, find

find

parent[x]에 저장된 값이 x와 동일하다면 자기자신이 부모다. 따라서 끝낸다.

같지 않다면 parent[x]값을 find(parent[x])값으로 갱신하도록 재귀호출한다.

 

union

a,b의 parent를 각각 구한 후 같지않다면 둘을 합친다. parent[rootB]에 rootA를 저장하면 간단하게 합칠 수 있다.

private static int find(int x){
   if(parent[x]==x) return x;
   return parent[x] = find(parent[x]);
}
private static void union(int a, int b){
   int rootA = find(a);
   int rootB = find(b);
   if(rootA == rootB) return;
   parent[rootB] = rootA;
}

---

3. 결과