BOJ) 바이러스 (2606, JAVA)

풀이

 

전형적인 find - union 문제라고 할 수 있겠다.

n 대의 컴퓨터가 연결되어 있고, 연결 관계가 주어진다. (그래프)

연결된 컴퓨터들 중 하나만 바이러스 걸려도 연결된 컴퓨터 모두 바이러스가 걸린다.

1번 컴퓨터가 바이러스 걸렸을 때, 몇 대의 컴퓨터가 추가적으로 바이러스 걸리는지 구하는 문제다.

 

풀이는 간단했다.

우선 parents 배열, find, union 메소드를 만들어 줬다.

그리고 입력을 받으면서 따로 graph에 저장하지 않고, 바로 find -union을 해줬다.

이후, 2번 ~ n번까지 컴퓨터를 돌면서 parent를 찾아 1번의 parent와 같다면 답에 더해줬다.

(union할 때, 더 큰수의 parent를 작은 수로 설정해서 아마 1번의 parents는 언제나 1일것이다. 하지만, 1번이 아니라 k번을 구할 때도 이 코드를 사용할 수 있게끔?? 1번의 parent도 따로 찾아줬다.)

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] parents;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int cases = Integer.parseInt(br.readLine());
        initParents(n);

        for(int i=0; i<cases; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            union(Math.min(left,right),Math.max(left,right));
        }
        int origin = find(1);   // 1번 컴퓨터
        int answer =0;
        for(int i=2; i<=n; i++) {
            if(find(i) == origin)    answer++;
        }
        System.out.println(answer);
        br.close();
    }

    private static int find(int val) {
        if(val == parents[val]) return val;
        return parents[val] = find(parents[val]);
    }

    private static void union(int left, int right) {
        left = find(left);
        right = find(right);
        if(left != right)   parents[right] = left;
    }

    private static void initParents(int n) {
        parents = new int[n+1];
        for(int i=1; i<=n; i++) parents[i] = i;
    }
}