[백준] 닭싸움 팀 정하기 1765번 Java

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

 

풀이 방법

유니온 파인드 문제이다

우선 F인 친구가 나오게 된다면, union을 한다.

반면 E가 나오게 된다면 enemy에 저장을 한 후, 모든 enemy를 돌며 enemy의 enemy를 union을 해주었다.

이후 집합의 수를 Set을 활용하여 세었다.

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    static int n, m;
    static int[] parents;
    static ArrayList<Integer>[] enemy;

    static int find(int a) {
        if (parents[a] == a) return a;
        parents[a] = find(parents[a]);
        return parents[a];
    }
    static void union(int a, int b) {
        int parA = find(a);
        int parB = find(b);
        if (parA != parB) {
            if (parA < parB) {
                parents[parB] = parA;
            }
            else {
                parents[parA] = parB;
            }
        }
        return;
        
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        parents = new int[n+1];
        enemy = new ArrayList[n+1];
        for (int i = 0;i <= n;i++) {
            parents[i] = i;
            enemy[i] = new ArrayList<>();
        }
        for (int i = 0;i < m;i++) {
            st = new StringTokenizer(br.readLine());
            if (st.nextToken().equals("F")) {
                union(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            }
            else {
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                enemy[a].add(b);
                enemy[b].add(a);
                
            }
        }

        for (int i = 1;i <= n;i++) {
            for (int k = 0;k < enemy[i].size();k++) {
                int enemyIdx = enemy[i].get(k);
                for (int j = 0;j < enemy[enemyIdx].size();j++) {
                    union(i, enemy[enemyIdx].get(j));
                }
            }
        }

        Set<Integer> ans = new HashSet<>();

        for (int i = 1;i <= n; i++) {
            find(i);            
            ans.add(parents[i]);
        }
        
        System.out.println(ans.size());
        return ;       
    }
}