[백준]1765: 닭싸움 팀 정하기(java)

문제

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

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 알고리즘을 사용해야한다고 생각했습니다.

친구인경우 union을 통해서 같은 부모로 만들어주면됩니다.

여기서 주의해야할점은 원수의 원수는 친구이므로 원수의 원수또한 union find를 통해서 같은 그룹으로 만들어주었습니다.

두개의 ArrayList 배열을 사용하여 친구, 원수를 담았습니다.

원수의 원수를 찾는 방법은 다음과 같습니다.

for(int i=1; i<=N; i++) {
    for(int j=0; j<enemyList[i].size(); j++) {
        int n = enemyList[i].get(j);
        for(int k=0; k<enemyList[n].size(); k++) {
            if(i==enemyList[n].get(k)) continue;
            friendList[i].add(enemyList[n].get(k));
            friendList[enemyList[n].get(k)].add(i);
        }
    }
}

현재 나는 i이고 원수는 n이다.

n의 원수들중 나(i)를 제외한 모든 원수들을 친구로 담아준다.

이 후에 친구 리스트들을 모두 union-find 알고리즘을 통해 부모를 통일시켜줍니다.

for(int i=1; i<=N; i++) {
    for(int j=0; j<friendList[i].size(); j++) {
        union(i, friendList[i].get(j));
    }
}

후에 부모가 다른 수 = 그룹의 수이기 때문에 Set을 통해서 담아주어 set의 크기를 답으로 반환하였습니다.

 

전체 코드

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

public class BJ_G1_1765_닭싸움팀정하기 {
    static int[] parent;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N, M;
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        ArrayList<Integer>[] enemyList = new ArrayList[N+1];
        ArrayList<Integer>[] friendList = new ArrayList[N+1];
        parent = new int[N+1];
        for(int i=1; i<=N; i++) {
            friendList[i] = new ArrayList<>();
            enemyList[i] = new ArrayList<>();
            parent[i] = i;
        }

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            if(st.nextToken().equals("E")) {
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                enemyList[a].add(b);
                enemyList[b].add(a);
            } else {
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                friendList[a].add(b);
                friendList[b].add(a);
            }
        }
        for(int i=1; i<=N; i++) {
            for(int j=0; j<enemyList[i].size(); j++) {
                int n = enemyList[i].get(j);
                for(int k=0; k<enemyList[n].size(); k++) {
                    if(i==enemyList[n].get(k)) continue;
                    friendList[i].add(enemyList[n].get(k));
                    friendList[enemyList[n].get(k)].add(i);
                }
            }
        }

        for(int i=1; i<=N; i++) {
            for(int j=0; j<friendList[i].size(); j++) {
                union(i, friendList[i].get(j));
            }
        }
        HashSet<Integer> hs = new HashSet<>();
        for(int i=1; i<=N; i++) {
            hs.add(parent[i]);
        }
        System.out.println(hs.size());
    }

    public static int find(int a) {
        if(parent[a] == a)
            return a;
        else
            return parent[a] = find(parent[a]);
    }
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if(a != b)
            parent[b] = a;
    }
}