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

🔗링크

1765 닭싸움 팀 정하기 Gold2

⚠️문제

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

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. 변수 선언은 아래 코드와 같이 하였다. 부모노드를 기록하는 parent배열, 라이벌을 2차원 배열로 표현해서 a라이벌이 b라면 rivalGraph[a][b] = true; 와 같은 형식으로 기록할 것이다. team은 마지막 팀장 수를 계산할 때 쓰일 배열이며, 친구 배열을 따로 두지 않은 것은 친구를 입력받을 때 동시에 팀을 맺어줄 것이기 때문에 필요하지 않았다.

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[] parent;
    static int N, M, result = 0;
    static int[] team;
    static boolean[][] rivalGraph;

2. 유니온 파인드 로직과 같이 초기에는 자기 자신을 팀장으로 설정한다. 이후 관계를 입력받을 때 친구라면 바로 엮어주고, 라이벌이라면 라이벌 배열에 기록한다.

        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            String relationship = st.nextToken();
            int student1 = Integer.parseInt(st.nextToken());
            int student2 = Integer.parseInt(st.nextToken());

            if (relationship.equals("E")) {
                rivalGraph[student1][student2] = true;
                rivalGraph[student2][student1] = true;
            }else{
                makeFriend(student1, student2);
            }
        }

3.라이벌의 라이벌을 친구로 만드는 코드이다. 보이듯 모든 사람을 탐색하면서 해당 사람의 라이벌의 라이벌리스트를 모두 친구를 만든다. 

        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(rivalGraph[i][j]){
                    for(int k = 1; k <= N; k++){
                        if(rivalGraph[j][k]) {
                            makeFriend(i, k);
                        }
                    }
                }
            }
        }

4. 팀 개수를 세는 로직이다. 모든 팀원을 돌면서 팀장이 누구인지 체크하고, 팀장의 수만 카운트 되기 때문에 배열 전체에서 0이 아닌 숫자만 결과값에 카운트한다.

        for(int i = 1; i <= N; i++) {
            team[findParent(i)]++;
        }

        for (int i : team) {
            if(i != 0){
                result ++;
            }
        }

5.아래 코드는 친구를 맺는 코드와 부모찾는 코드이다. 친구는 팀이 같으니 팀장를 공유하도록 구현했으며,(팀장 번호가 높은 경우가 팀을 흡수함.), 해당 팀원의 팀장을 찾는 코드는 재귀적으로 팀원 자기 자신이 팀장일 경우 멈추도록 구현했다.

    static void makeFriend(int student1, int student2) {
        if (findParent(student1) != findParent(student2)) {
            if (student1 > student2) {
                parent[findParent(student2)] = findParent(student1);
            }else{
                parent[findParent(student1)] = findParent(student2);
            }
        }
    }

    static int findParent(int i) {
        if (parent[i] == i) {
           return i;
        }
        return parent[i] = findParent(parent[i]);
    }

---

✔전체 코드

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[] parent;
    static int N, M, result = 0;
    static int[] team;
    static boolean[][] rivalGraph;

    public static void main(String[] args) throws IOException {

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        team = new int[N + 1];
        parent = new int[N + 1];
        rivalGraph = new boolean[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            String relationship = st.nextToken();
            int student1 = Integer.parseInt(st.nextToken());
            int student2 = Integer.parseInt(st.nextToken());

            if (relationship.equals("E")) {
                rivalGraph[student1][student2] = true;
                rivalGraph[student2][student1] = true;
            }else{
                makeFriend(student1, student2);
            }
        }

        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(rivalGraph[i][j]){
                    for(int k = 1; k <= N; k++){
                        if(rivalGraph[j][k]) {
                            makeFriend(i, k);
                        }
                    }
                }
            }
        }

        for(int i = 1; i <= N; i++) {
            team[findParent(i)]++;
        }

        for (int i : team) {
            if(i != 0){
                result ++;
            }
        }

        System.out.println(result);
    }

    static void makeFriend(int student1, int student2) {
        if (findParent(student1) != findParent(student2)) {
            if (student1 > student2) {
                parent[findParent(student2)] = findParent(student1);
            }else{
                parent[findParent(student1)] = findParent(student2);
            }
        }
    }

    static int findParent(int i) {
        if (parent[i] == i) {
           return i;
        }
        return parent[i] = findParent(parent[i]);
    }
}

😄결과

유니온 파인드를 구현하는데 애를 먹었다. 다 완성해놓고 코드가 제대로 실행이 안되서 30분 내내 확인해보니 유니온 파인드 코드내에 findParent를 빼먹었었다. 많은 문제를 풀고 알고리즘에 익숙해져야 실수를 줄일 수 있을 것 같다.