[백준][C++] 12893번: 적의 적 <232>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

12893번: 적의 적

 

생각의 흐름

적의 적을 구한다는 점 에서, 분리집합 즉, Union Find가 가장 먼저 떠올랐다.

(ps 다른 방식으로는 1, -1, 1, -1 이런식으로 표식을 남기는 방법을 떠올렸다)

 

우선 Union Find 를 이용할 것 인데, parent, enemyGroup 이라는 배열을 이용할 것 이다.

처음 모든 정점은 자기 자신이 parent가 되도록 초기화 해준다.

 

만약 input으로 A 와 B가 들어왔다고 해보자.

A 와 B 각각이 속한 group을 구해서 두 그룹이 같다면, 즉 A와 B가 동지라면 모순이다. 서로 다른 집합에 있어야하기 때문이다.

A 와 B 의 그룹이 다르다면 => A의 적은 B의 친구로, B의 적은 A의 친구로 만든다.

 

대략적인 코드는 다음과 같을 것 이다.

while (A, B) {
    if (A와 B가 동지 == true) then 이론이 성립하지 않는다.
    else {
        if (A의 적이 존재한다면) then A의 모든 적을 B의 동지로 설정한다;
        else A의 적으로 B를 추가한다.

        if (B의 적이 존재한다면) then B의 모든 적을 A의 동지로 설정한다;
        else B의 적으로 A를 추가한다.
    }
}

위 흐름을 이해한 후, 다음 코드를 보면 이해할 수 있을것 이다.

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define MAX 1000001

int N, M;
int parent[2001];
int enemyGroup[2001];

int find(int u) {
    if(parent[u] == u) {
        return u;
    }

    return parent[u] = find(parent[u]);
}

void join(int a, int b) {
    int ap = find(a);
    int bp = find(b);

    if(ap == bp) {
        return;
    }
    parent[ap] = bp;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

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

    int a, b;
    for(int i = 0; i < M; i++) {
        cin >> a >> b;
        int ap = find(a);
        int bp = find(b);

        if(ap == bp) {
            cout << 0;
            exit(0);
        }
        int& aEnemy = enemyGroup[a];
        int& bEnemy = enemyGroup[b];

        if(aEnemy != 0) { // 적 그룹이 이미 있는경우
            join(aEnemy, b);
        }else{
            aEnemy = b;
        }

        if(bEnemy != 0) {
            join(bEnemy, a);
        }else{
            bEnemy = a;
        }
    }

    cout << 1;
    return 0;
}