[Python] 백준 23259 Celebrity

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

23259번: Celebrity

1. 접근 방법

그래프의 동형 확인은 매우 어려운 작업이다.

그나마 그래프의 동형을 판별하는 몇 가지 방법을 기준으로 하나하나 분류하려 시도했는데, 너무 많은 조건을 고려해야 할 것 같아서 그래프의 조건을 기준으로 동형을 판별하는 것은 포기하고, 브루트 포스로 탐색했다.

점이 5개로 고정이므로, 각 간선 번호를 0~9번으로 하여 각 별의 상태를 비트연산으로 계산한 숫자로 처리했다.

 

 

2. 풀이 코드

🖥python 코드

from itertools import permutations
import sys
input = sys.stdin.readline


def star_to_num(star: list) -> int:
    star_now = 0
    for a, b in star:
        if a > b:
            a, b = b, a
        star_now |= 1 << pair_to_num(a, b)
    return star_now


def pair_to_num(a: int, b: int) -> int:
    # 두 점 쌍 a, b로 지정할 수 있는 숫자로 변경
    # a, b 값에 따라 지정 0 ~ 9
    if a == 0:
        return b - 1
    elif a == 1:
        return b + 2
    elif a == 2:
        return b + 4
    elif a == 3:
        return b + 5


n = int(input())
check = [0] * 1024
perms = list(permutations(range(5), 5))
for _ in range(n):
    m = int(input())
    star = []
    for _ in range(m):
        a, b = map(int, input().split())
        star.append((a - 1, b - 1))
    star_num = star_to_num(star)
    if check[star_num] == 2:
        continue
    # star의 쌍을 회전하면서 다른 대응 가능 숫자 확인
    unique = True
    similar_star_nums = []
    # 점 교환 가능한 모든 위치 확인
    for perm in perms:
        similar_star = []
        # 점 회전
        for a, b in star:
            similar_star.append((perm[a], perm[b]))
        similar_star_num = star_to_num(similar_star)
        if check[similar_star_num]:
            unique = False
        similar_star_nums.append(similar_star_num)
    # 지금 점이 유일한지
    if unique:
        check[star_num] = 1
    else:
        for similar_star_num in similar_star_nums:
            check[similar_star_num] = 2

beautiful_stars_count = check.count(1)

print(beautiful_stars_count)

📕코드 해설

각 점을 순서대로 다음을 확인한다.

1. 지금 별에 대응시킬 수 있는 숫자가 얼마인지 (비트연산)

    1.1. 만약 그 숫자를 사용할 수 있다면 추가 탐색

    1.2. 그 숫자를 사용할 수 없다면, 다음 별로 넘어가기

2. 해당 별에 대한 숫자를 사용할 수 있으면, 해당 별과 동형인 모든 그래프 탐색

 

- 별에 해당하는 숫자 찾기

가능한 간선은 총 10가지이고, 0과 1일 때 0으로, 4와 5일 때 9로 대응시켰다.

이후, 각 별의 구성에서 간선 번호를 기준으로 비트 연산으로 대응하는 별을 계산했다.

 

- 다른 동형인 별 탐색

5개의 숫자를 5개의 숫자로 치환하는 방법은 5! =120가지이고, 이를 미리 계산해두었다.

각각의 동형인 별을 탐색하고, 모든 동형을 다시 확인하면서, 동형인 별 중 불가능한 게 있다면 모두 2로, 겹치지 않는다면 처음 확인한 별만 1로 저장한다.

 

 

3. 생각 정리

그래프 이론에서 비트 연산까지 정말로 다양한 지식을 활용해 풀었다.

푸는 과정에는 정말 힘들지만, 다양한 이론을 같이 사용할 수 있는 것을 알게 되는 측면에서 절말 재밌고, 도움 되는 문제였던 것 같다.