백준 2606: 바이러스 (java)

1717번이랑 거의 똑같은 문제인데 못풀었다.

그래서 1717번 포스팅으로 돌아가서 다시 풀 수 있는가 NO로 바꿈..

 

그리고 나는 유니온 파인드로 풀었는데 보통 DFS로 많이 푸는듯하다.

DFS로 풀면 코드가 좀 더 간결해지는듯하나 속도랑 메모리 차이는 거의 없다.

 

DFS 풀이

 

https://zzang9ha.tistory.com/40

[백준] 2606번: 바이러스(DFS, BFS)

 

Union-Find 알고리즘 (그림 설명)

 

https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Union-Find

[알고리즘] 유니온 파인드 (Union-Find)

 

---

 

알고리즘

그래프: Union-Find

 

체감 난이도

★ ★ ★ ☆ ☆

 

다시 풀 수 있는가?

NO

---

 

1. union

    public void union(int a, int b) {
        int u = find(a);
        int v = find(b);

        if (u == v) {
            return;
        }

        // 더 작은 값이 root 가 되도록 설정
        if (u < v) {
            arr[v] = u;
        }
        else {
            arr[u] = v;
        }
    }

 

2. find

    public int find(int r) {
        if (r == arr[r]) {
            return r;
        }

        return arr[r] = find(arr[r]);
    }

 

 

전체 코드 ▼

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

public class BOJ2606 {
    int[] arr;
    int a, b, cnt;

    public int find(int r) {
        if (r == arr[r]) {
            return r;
        }

        return arr[r] = find(arr[r]);
    }

    public void union(int a, int b) {
        int u = find(a);
        int v = find(b);

        if (u == v) {
            return;
        }

        // 더 작은 값이 root 가 되도록 설정
        if (u < v) {
            arr[v] = u;
        }
        else {
            arr[u] = v;
        }
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        for (int i = 1; i <= N; i++) {
            arr[i] = i;
        }

        int E = Integer.parseInt(br.readLine());
        for (int i = 1; i <= E; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            union(a, b);
        }

        for (int i = 2; i <= N; i++) {
            if (find(i) == 1) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new BOJ2606().solution();
    }
}