백준 1765번 (java) 유니온 파인드

백준 1765번 닭싸움 팀 정하기

관찰

일단 편을 가르는 문제는 전형적인 유니온 파인드 문제라고 할 수 있다.

1. 내 친구의 친구는 내 친구이다.

이 조건은 유니온 파인드의 특징이라고 할 수 있다.

어려운 것은 2번 조건인데

2. 내 원수의 원수도 내 친구이다.

원수를 저장해서 원수의 원수를 찾아주고 원수의 원수를 union 시켜서 도전해보자

---

정답 코드

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

public class Main {

    static int n,m; // 1000,5000
    static int[] p,r;
    static int[][] eList;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());

        p = new int[n + 1];
        r = new int[n + 1];
        eList = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            p[i] = i;
            r[i] = 1;
        }
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            char tmp = st.nextToken().charAt(0);
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (tmp == 'E') {
                // 원수 담아주기
                eList[a][b] = 1;
                eList[b][a] = 1;
            } else {
                // 친구는 union
                if(union(a,b)) cnt++;
            }
        }

        // 담아준 원수를 바탕으로 친구를 찾아서 union
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                if(eList[i][j]==1) {
                    for(int k=1;k<=n;k++) {
                        if(i != k && eList[k][j]==1) {
                            if(union(i,k)) cnt++;
                        }
                    }
                }
            }
        }

        System.out.println(n - cnt);

    }

    public static boolean union(int a,int b){
        int A = find(a);
        int B = find(b);
        if(A == B) return false;
        if(r[A] > r[B]) {
            r[A] = B;
            p[B] = A;
        }
        else {
            r[B] = A;
            p[A] = B;
        }
        return true;
    }

    private static int find(int b) {
        if(b == p[b]) return b;
        else return p[b] = find(p[b]);
    }

}

풀이

1. 친구일 때는 그냥 유니온 해서 한 그룹으로 묶어준다.

2. 원수일 때는 원수를 따로 관리해준다.

2-1) 2차원 배열로 만들어서 편리하게 사용 (인접행렬 느낌)

3. 3중 포문으로 원수의 원수 관계에 있는 둘을 유니온 한다.

4. 유니온 파인드를 성공한 갯수를 세어준다. (연결된 횟수)

5. 전체 인원 - 연결된 횟수 => 정답

---

마무리

원수의 원수 관계를 어떻게 관리할지가 핵심인 문제였다. 원수의 원수의 원수의 원수 관계를 처리를 어떻게 하는지 고민을 많이 했던 것 같다.
인접행렬처럼 문제를 풀 수 있었는데 나중에 그래프 문제에서도 사용할 수 있을 것 같다. (길이가 2 떨어진 곳들 처리)