21316번: 스피카

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

21316번: 스피카

알고리즘 분류에는 그래프이론, 애드 혹(ad-hoc) 이라고 써있는데, 애드 혹이 뭔가 해서 검색해보니 

정형화된 방법론이 아니라, 그 문제를 풀기 위한 창의적인 아이디어를 떠올려야 하는 경우에 애드혹 문제 라고 한다고 한다.

 

해당 문제도 풀 수 있는 방법이 여러 개 있을 것 같은데, 나는 인접리스트 방식으로 그래프를 받은 후에 1~12까지 탐색하면서 연결된 원소가 3개인 경우에 그 각각의 원소에 연결되어 있는 원소의 합을 구해서 그 합이 6인 경우를 출력하였다. 제일 밝게 빛나는 원소의 특징이 뭐가 있을까를 그려보다가 발견한 규칙(?) 이다.

 

import sys
input = sys.stdin.readline
arr = [[] for _ in range(13)]

for _ in range(12):
    x, y = map(int, input().split())
    arr[x].append(y)
    arr[y].append(x)
    
for i in range(1, 13):
    if (len(arr[i]) == 3):
        s = 0
        for j in arr[i]:
            s += len(arr[j])
        if (s == 6):
            print(i)
            break