백준 2606 바이러스 Java

다양한 방법으로 풀 수 있는 바이러스 문제이다.

대표적인 방법이 DFS, BFS이다. 

나도 몇 달전에 BFS로 풀었었던 문제인데

이 문제를 유니온 파인드를 활용해 풀면 DFS보다 실행 속도를 훨씬 빠르게 해결할 수 있다.

https://dundung.tistory.com/103

유니온 파인드

문제의 내용은

1부터 N까지의 컴퓨터들이 연결된 M개의 쌍이 주어지고

1번 컴퓨터가 감염되었을 때 바이러스가 옮는 컴퓨터의 수를 출력하면 된다.

 

유니온 파인드를 활용해 컴퓨터의 쌍을 집합으로 표현하고

2부터 N까지의 수들을 Find 메소드를 통해

1번 컴퓨터로부터 감염되는 컴퓨터를 찾고 개수를 세면 된다.

주의해야 할 점은 1이 반드시 루트가 아니라는 점이다.

 

for(int i=2; i<=n; i++) {

    if(find(i) == 1) {

    ans++;

    }

}

처음에 코드를 이렇게 작성했었는데

틀린 방법이였다.

 

1이 무조건 루트라는 얘기는 없기 때문이다.

1도 어떤 집합에 속해있을 수 있다는 얘기이다

만약 

3 1

1 2

2 4 

이렇게 컴퓨터의 쌍이 주어졌다면

감염되는 컴퓨터는 2, 3, 4 => 3대의 컴퓨터지만

 if(find(i) == 1) {

    ans++;

    }

이렇게 코드를 썼다면 

1의 루트가 3이고

1로 인해 감염되는 컴퓨터들은 find메소드를 호출했을 때

전부 3을 리턴하기 때문에 ans는 증가되지 않고 0이 출력된다.

때문에 감염되는 컴퓨터를 찾을 때는

if(find(i) == find(1)) {

    ans++;

    }

이런 식으로 1의 루트와 비교해야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Q2606 {
    public static int [] parent;
    
    public static int find(int x) {
        if(parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
    
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if(x != y) {
            parent[y] = x;
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        parent = new int[n+1];
        for(int i=1; i<=n; i++) {
            parent[i] = i;
        }
        int m = Integer.parseInt(reader.readLine());
        for(int i=0; i<m; i++) {
            StringTokenizer st = new StringTokenizer(reader.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            union(x, y);
        }
        int ans = 0;
        for(int i=2; i<=n; i++) {
            if(find(1) == find(i)) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}