Celebrity( BOJ 23259 )

문제 : https://www.acmicpc.net/problem/23259

23259번: Celebrity

 

문제 파악하기

주어진 N개의 그래프 중 동형인 그래프가 없이 유일한 모양인 그래프의 개수를 찾는 문제입니다. N은 최대 10,000개이지만 다행히 입력되는 모든 그래프의 정점은 항상 5개이기 때문에 모든 경우의 수를 확인하여 문제를 해결할 수 있습니다.

 

문제 해결하기

우선, 그래프가 동형인지 아닌지 확인하는 방법부터 찾아야 합니다. 그래프가 서로 동형이란 의미는 연결된 정점의 상태가 동일하다는 의미입니다. 문제에서 확인할 수 있듯이 별 A와 별 B는 달라보이지만 잘 보면 정점 간 연결된 상태가 똑같습니다. 이처럼 정점 간 연결된 상태가 같은지 확인하기 위해서는 정점의 번호를 바꿔가면서 확인해야 합니다. 모든 위치의 정점을 1번부터 5번까지 매칭하면서 정점 간 연결된 상태를 확인하면 동형인지 구분할 수 있습니다. 그리고 이렇게 확인하기 위해서는 next_permutation을 사용하여 1부터 5까지의 모든 순열을 구한 다음, 각각의 정점에 대입하면 됩니다.

 

그럼 동형인지 확인했으니, 이제는 기록하는 방법을 생각해봅시다. 모든 그래프는 나온 횟수를 표시해야 합니다. 그래야 마지막에 딱 1번 나온 그래프의 개수를 셀 수 있습니다. 그럼 어떻게 그래프를 기록할 수 있을까요? 다행히 정점이 총 5개이기 때문에 나올 수 있는 간선의 개수는 10개입니다. 이러면 우리는 비트 연산자를 사용해서 십진수의 모습으로 간선의 현황을 기록할 수 있습니다. (1, 1)부터 (4, 5)까지 순서대로 간선이 있다면 1, 없다면 0으로 표현한 2진수를 10진수로 변환한 다음, 배열의 인덱스로 활용하여 나온 횟수를 기록한 다음, 모든 그래프의 탐색이 끝난 후에는 0부터 1023까지의 숫자를 확인하면서 그래프가 등장한 횟수를 세면 됩니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#define NMAX 10
using namespace std;
 
int N, E, a, b;
int Edge[NMAX][NMAX], tEdge[NMAX][NMAX];
 
int tmp, ret;
vector< int > num;
int check[1<<NMAX];
 
int main() {
    scanf("%d", &N);
    while(N--) {
        // init
        memset(Edge, 0, sizeof(Edge));
 
        // input
        scanf("%d", &E);
        for(int i=1;i<=E;i++) {
            scanf("%d %d", &a, &b);
            a--; b--;
 
            Edge[a][b] = Edge[b][a] = 1;
        }
 
        // 순열
        num.clear();
        for(int i=0;i<5;i++) num.push_back(i);
        do {
            memset(tEdge, 0, sizeof(tEdge));
 
            // 비트마스킹
            tmp = 0;
            for(int i=0,t=0;i<5;i++) {
                for(int j=i+1;j<5;j++,t++) {
                    tmp |= (Edge[num[i]][num[j]]<<t);
                }
            }
 
            // 종료 조건
            if(check[tmp]) {
                check[tmp]++;
                break;
            }
 
        }while(next_permutation(num.begin(), num.end()));
 
        // 등장한 적이 없으면 한 가지 추가
        if(!check[tmp]) check[tmp]++;
    }
 
    // 아름다운 별의 개수
    for(int i=0;i<(1<<NMAX);i++) {
        if(check[i] == 1) ret++;
    }
 
    // 결과 출력
    printf("%d", ret);
}

후기

그래프의 동형을 찾는 방법은 한 번 기억하면 잊기 힘든 방법입니다. 동형인지 확인하는 문제는 여러 가지 있지만 최근에 풀어본 문제로는 Atcoder에서 진행했던 이 문제(https://atcoder.jp/contests/abc232/tasks/abc232_c)가 생각납니다. 기본적인 문제라서 한번 풀어볼 문제로 추천합니다.