백준 1765 닭싸움 팀 정하기.java

문제

누르면 이동합니다.

문제 속 힌트

• 내 친구의 친구는 내 친구이다, 내 원수의 원수도 내 친구이다
• 친구이면 같은 팀에 속해있어야 하며
  • 친구끼리 팀으로 묶는다. Union Find
• 입력에서, 입력은 모순이 없음이 보장된다. 즉, 두 학생이 동시에 친구이면서 원수인 경우는 없다.

추가 조건

Union-Find에서 아래 조건이 추가되었다.

• 친구 끼리만 같은 팀이 될 수 있다.
• 누군가의 원수의 원수는 친구다.

원수를 제외하며 묶어야 한다.

풀이 보기

설명

원수의 원수는 친구다.만 해결하면 쉽다.

어떤 사람과 원수인 관계는 그 반대로도 적용되어야 한다.

예제에서,

• (1, 4)는 원수
• (3, 5)는 친구
• (4, 6)은 친구
• (1, 2)는 원수

일단 친구 관계는 바로 묶어줘도 상관없다.

하나씩 그려보자.

이 상태에서,

(1, 4) 원수 관계

(1, 2) 원수 관계를 추가

마지막 그림을 보면 2와 4는 같은 원수를 공유하고 있다.
따라서 2와 4는 친구다!

결론

• 친구 관계는 바로 묶어준다.
• 원수인 경우 원수 관계로 추가
  • A - B 원수에서, 누군가 이미 A와 원수라면 누군가와 B는 친구다.
  • 그 반대로도 친구다. 묶자.

코드

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static int[] friendSet;
    static int ans;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        friendSet = new int[n+1];
        for(int i=1;i<=n;i++) friendSet[i] = i;
        ans = n;

        int[] enemy = new int[n+1];
        for(int i=0;i<m;i++){
            char type = sc.next().charAt(0);
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();

            if(type == 'E'){
//                원수인 경우. 원수에 추가하고 다른 원수랑 친구맺어주기
                if(enemy[n1] == 0) enemy[n1] = n2;
                else{
//                    enemy[n1], n2 유니온
                    union(enemy[n1], n2);
                }
                if(enemy[n2] == 0) enemy[n2] = n1;
                else{
//                    enemy[n2], n1 유니온
                    union(enemy[n2], n1);
                }
            }else{
//                친구인 경우. 그냥 union
                union(n1, n2);
            }
        }
        System.out.println(ans);
    }

    static int find(int idx){
        if(friendSet[idx] == idx) return idx;
        return friendSet[idx] = find(friendSet[idx]);
    }

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

        if(p1 != p2) {
            friendSet[p2] = p1;
            ans--;
        }
    }
}