BOJ 1765 닭싸움 팀 정하기

https://www.acmicpc.net/problem/1765

문제

닭싸움은 월드의 전통이다. 이번 캠프에서도 어김없이 닭싸움 대회가 열렸다. 그런데, 닭싸움을 하기 위해서는 반드시 누가 우리 편이고, 누가 우리 편이 아닌지를 알아야 할 것이다. 닭싸움의 팀을 정하는 원칙은, 평소 학생들의 인간관계에 따라 다음과 같이 정리할 수 있다.

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

이 때 두 학생이 친구이면 같은 팀에 속해있어야 하며, 같은 팀에 속해 있는 사람들끼리는 전부 친구여야 한다.

학생들의 인간관계가 주어지면, 닭싸움을 위한 팀 정하기를 할 때, 최대 얼마나 많은 팀이 만들어질 수 있는지 알아내는 프로그램을 작성하시오.

---

입력

첫째 줄에 학생의 수 n이 주어진다. 각 학생들은 1부터 n까지 번호가 매겨져 있다. (2 ≤ n ≤ 1000)

둘째 줄에 학생 간의 인간관계 중 알려진 것의 개수 m이 주어진다. (1 ≤ m ≤ 5000)

다음 m개의 줄에는 한 줄에 한 개씩, 학생 간의 인간관계가 F p q 혹은 E p q의 형태로 공백으로 구분되어 주어진다. (1 ≤ p < q ≤ n)

첫 번째 글자가 F인 경우에는 p와 q가 친구인 것이고, E인 경우는 p와 q가 원수인 경우이다.

입력은 모순이 없음이 보장된다. 즉, 두 학생이 동시에 친구이면서 원수인 경우는 없다.

---

출력

첫째 줄에, 가능한 최대 팀 개수를 출력한다.

---

예제 입력 1

6
4
E 1 4
F 3 5
F 4 6
E 1 2

예제 출력 1

3

---

힌트

1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다.

---

코드

union-find로 풀어야 할 것 같다는 느낌은 왔는데, 코드를 어떻게 작성해야 할지 잘 생각나지 않는 문제였다.

막상 문제를 푼 코드를 보면 그리 복잡하지는 않다.

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

public class Main {

    static int n;
    static int[] parents;
    static List<Integer>[] enemies;
    static List<Integer>[] friends;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        enemies = new List[n + 1];
        friends = new List[n + 1];
        parents = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            enemies[i] = new ArrayList<>();
            friends[i] = new ArrayList<>();
            parents[i] = i;
        }

        int m = Integer.parseInt(br.readLine());
        while (m-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String type = st.nextToken();
            int p = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());

            if(type.equals("E")) {
                enemies[p].add(q);
                enemies[q].add(p);
            } else {
                friends[p].add(q);
                friends[q].add(p);
            }
        }

        int answer = calculateMaxTeamCount();

        System.out.println(answer);
    }

    static int calculateMaxTeamCount() {
        for (int i = 1; i <= n; i++) {
            // 원수의 원수를 union-find를 통해 같은 팀으로 만듦
            for (int enemy: enemies[i]) {
                for (int enemyOfEnemy: enemies[enemy]) {
                    union(i, enemyOfEnemy);
                }
            }
            
            // 친구, 친구의 친구를 union-find를 통해 같은 팀으로 만듦
            for (int friend: friends[i]) {
                union(i, friend);
                for (int friendOfFriend: friends[friend]) {
                    union(i, friendOfFriend);
                }
            }
        }
        
        // n명의 학생들이 속한 팀의 수를 계산
        Set<Integer> teams = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            teams.add(parents[i]);
        }

        return teams.size();
    }

    static int find(int s) {
        int parent = parents[s];
        if(parent == s) {
            return s;
        }

        return parents[s] = find(parent);
    }

    static void union(int s1, int s2) {
        int p1 = find(s1);
        int p2 = find(s2);

        if(p1 == p2) {
            return;
        }

        if(p1 < p2) {
            parents[p2] = p1;
            return;
        }

        parents[p1] = p2;
    }
}