[BaekJoon] 1765 닭싸움 팀 정하기 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int[] parents; // 각 학생의 친구를 나타내는 배열
    static int[] opposite; // 각 학생의 원수 중 하나를 나타내는 배열

    static void input() {
        Reader scanner = new Reader();

        n = scanner.nextInt();
        parents = new int[n + 1];
        opposite = new int[n + 1];
        // 초기화
        for(int student = 1; student <= n; student++) {
            parents[student] = student;
        }

        int m = scanner.nextInt();
        for(int count = 0; count < m; count++) {
            String type = scanner.next();
            int student1 = scanner.nextInt();
            int student2 = scanner.nextInt();

            if(type.charAt(0) == 'E') { // 만약 두 학생이 원수라면
                // 만약 아직 두 학생 모두 원수인 학생이 정해지지 않다면
                // 두 학생 모두에게 현재 각자의 원수인 학생을 opposite에 설정한다
                if(opposite[student1] == 0 && opposite[student2] == 0) {
                    opposite[student1] = student2;
                    opposite[student2] = student1;
                }
                // 학생1의 원수는 정해져있지 않고 학생2의 원수는 정해져있다면
                // opposite 배열에 있는 학생2의 원수와 학생1을 같은 팀으로 묶는다
                // 같은 팀으로 묶는 작업은 Union-Find를 이용하여 진행한다
                //  - 두 학생 중 더 작은 번호의 학생의 번호로 같은 팀으로 묶는다
                else if(opposite[student1] == 0) {
                    union(opposite[student2], student1);
                }
                // 위 경우 모두 아니라면, 즉 학생1의 원수만 정해져있거나, 두 학생 모두의 원수가 정해져있다면
                // opposite 배열에 있는 학생1의 원수와 학생2를 같은 팀으로 묶는다
                else {
                    union(opposite[student1], student2);
                }
            } else if(type.charAt(0) == 'F') { // 두 학생이 친구라면
                // 두 학생을 같은 팀으로 묶는다
                union(student1, student2);
            }
        }
    }

    static int findParent(int student) {
        if(parents[student] == student) return student;
        return parents[student] = findParent(parents[student]);
    }

    static void union(int student1, int student2) {
        int parent1 = findParent(student1);
        int parent2 = findParent(student2);

        if(parent1 != parent2) {
            if(parent1 < parent2) parents[parent2] = parent1;
            else parents[parent1] = parent2;
        }
    }

    static void solution() {
        int answer = 0; // 팀 개수
        Set<Integer> visited = new HashSet<>(); // 방문한 팀을 저장하기 위한 Set
        // 1번 학생부터 n번 학생까지 순회하면서 각 학생의 팀을 얻어오고, 이를 활용하여 팀의 개수를 구한다
        for(int student = 1; student <= n; student++) {
            int parent = findParent(student); // 각 학생의 팀을 얻어온다
            // 만약 아직 방문하지 않은 팀이라면
            if(visited.add(parent)) {
                answer++; // 팀 개수를 1 증가시킨다
            }
        }

        System.out.println(answer);
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}