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

문제 링크: https://www.acmicpc.net/problem/1765

1765번: 닭싸움 팀 정하기

<문제 풀이> Union-Find, DFS, 집합, set, 자료구조

 

문제에 나와있는 두 가지 인간관계에 따라 Union-Find 알고리즘을 사용해서 같은 친구이면 같은 집합으로 만들어주고 집합의 개수를 세어주면 됩니다.

 

1. 내 친구의 친구는 내 친구이다.

이 부분은 단순히 Union-Find 알고리즘을 이용해서 같은 집합으로 만들어주면 끝입니다.

 

2. 내 원수의 원수도 내 친구이다.

문제에서 입력으로 주어진 원수 관계를 통해서 원수 인접 리스트를 만듭니다.

 

그다음 각각의 사람 i에 대해서 i의 원수의 원수를 찾아서 친구로 만드는 DFS를 구현하면 됩니다.

 

원수의 원수를 찾는 거니깐 DFS의 base case는 깊이가 2가 될 때입니다.

깊이가 2가 될 때, i와 깊이 2에서 발견한 사람을 Union으로 같은 집합으로 만들어주면 됩니다.

 

이를 구현하기 위해선 DFS의 파라미터는 다음 3가지를 가지고 있어야 합니다.

 

start : 사람 i의 번호

cur : 현재 바라보고 있는 원수의 번호

k : dfs의 깊이

 

각각의 사람 i에 대해서 DFS를 모두 호출하면 집합이 완성됩니다.

 

이때 parent 배열로 집합의 개수를 구하기 위해선 각각의 사람 i에 대해서 Find(i) 연산을 해주어야 합니다.

왜냐하면 Union-Find는 path-compression으로 구현되기 때문에 A, B가 같은 집합이라고 해서 parent[A]와 parent[B]가 같다는 것을 보장하지 않습니다.

같은 집합이면 parent[i]가 같다는 것을 보장하기 위해서 각각의 사람 i에 대해서 Find(i)를 호출하면 됩니다.

그러면 Find(i)를 호출하면서 부모를 다시 갱신하기 때문에 같은 집합일 때 같은 parent[i]을 가지게 됩니다.

 

이렇게 parent 배열을 완성했으면 set 자료구조에 모든 parent[i] 값을 넣어줍니다.

 

그러면 set 자료구조의 사이즈가 집합의 크기가 되고, 이는 가능한 팀의 최대 개수가 됩니다.

 

 

 

 

<C++소스코드>

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
 
int n, m;
 
vector<int> adj[1001]; // 학생 i에 대한 원수 인접리스트
int parent[1001];
bool visited[1001];
unordered_set<int> teams;
int Find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = Find(parent[x]);
}
 
void Union(int x, int y) {
    int xParent = Find(x);
    int yParent = Find(y);
    if (xParent < yParent) parent[yParent] = xParent;
    else parent[xParent] = yParent;
}
 
//start 번호를 가진 사람의 원수의 원수를 찾아서 친구로 만드는 DFS
void dfs(int start, int cur, int k) {
    if (k == 2) { // 원수의 원수가 존재하면
        Union(start, cur); // start와 원수의 원수를 친구로 만든다.
        return;
    }
 
    for (auto next : adj[cur]) { // cur의 원수들을 확인
        if (visited[next])continue; // 이미 확인한 원수이면 무시
        visited[next] = true;
        dfs(start, next, k + 1);
        visited[next] = false;
    }
 
 
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> n >> m;
 
    //Union-find init
    for (int i = 1; i <= n; i++) parent[i] = i; 
    
    for (int i = 0; i < m; i++) {
        char c; cin >> c;
        int p, q; cin >> p >> q;
        if (c == 'E') { // E 일 때는 p,q를 원수로 만든다. 
            adj[p].push_back(q);
            adj[q].push_back(p);
        }
        else if (c == 'F') { //F 일 때는 p, q를 친구로 만들면 됨
            Union(p, q);
        }
    }
    for (int i = 1; i <= n; i++) { //모든 사람에 대해서
        visited[i] = true;
        dfs(i,i, 0); //원수의 원수를 찾아 친구로 만든다.
        visited[i] = false;
    }
 
    // 모든 원소에 대해 Find 연산을 해야 같은 집합인 원소들의 parent 값이 같아짐 -> path-compression
    for (int i = 1; i <= n; i++) {
        Find(i); 
    }
    
    //set 자료구조에 각 원소의 부모를 넣으면 집합을 대표하는 부모들만 남음
    for (int i = 1; i <= n; i++) {
        teams.insert(parent[i]);
    }
    cout << teams.size(); //set 자료구조의 사이즈가 집합의 크기
    
    return 0;
 
}