[Python/파이썬] 백준 21316번 스피카

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

코드

from collections import defaultdict, deque

graph = [[] for _ in range(13)]
for _ in range(12):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)


def bfs(start):
    dist = [12]*13
    dist[start] = 0
    q = deque([start])

    while q:
        now = q.popleft()
        for nx in graph[now]:
            if dist[nx] > dist[now]+1:
                q.append(nx)
                dist[nx] = dist[now]+1

    result = defaultdict(int)
    for i in range(1, 13):
        result[dist[i]] += 1
    return result


for i in range(1, 13):
    if len(graph[i]) == 1:
        result = bfs(i)
        if result[1] == 1 and result[3] == 3:
            print(graph[i][0])
            break

 

해당 문제는 애드혹 문제다.

애드혹(Ad Hoc)이란?
"이것을 위해" 즉 "특별한 목적을 위해서"라는 뜻의 라틴어로, 일반적으로 다음을 나타낸다.
1. 특정한 문제나 일을 위해 만들어진 관습적인 해결책
2. 일반화할 수 없는 해결책
3. 어떤 다른 목적에 적응시킬 수 없는 해결책

출처: https://ko.wikipedia.org/wiki/%EC%95%A0%EB%93%9C%ED%98%B9

즉, 이 문제에만 적용되는 풀이가 필요하다는 말이다. 

나는 이 문제를 아래와 같이 풀었다.

 

이웃이 하나뿐인 점에서 BFS를 수행하여 시작점에서 거리가 1인 노드가 1개이고, 거리가 3인 노드가 3개인 경우에 시작점 옆 점이 스피카라는 것을 알았다. 

 

그래서 이웃이 1개뿐인 4개의 점에 대해 이것을 시작점으로 BFS를 수행하고 각 점까지의 최단거리를 구하여 리턴하도록 만들었다. 그리고 이 최단거리를 확인하여 거리가 1인 노드가 1개이고, 거리가 3인 노드가 3개라면 이 때 거리가 1인 노드를 출력하고 반복문을 탈출하도록 했다.

 

근데 풀고 나서 생각해보니 BFS도 아니고 그냥 그래프 탐색인 것 같다. BFS는 최적의 해를 구하고 탐색을 그만하도록 구현하는 것이 일반적인데 모든 노드를 다 탐색했기 때문이다.

 

사실 풀 때는 애드혹 유형인지도, 애드혹 유형이 무엇인지도 몰랐다. 이래도 되나? 싶게 풀었는데, 문제 유형을 보니 이렇게 푸는게 맞는것 같다. 제출한 뒤에 다른 사람들의 풀이를 보니 다들 개성있게 푼 것을 볼 수 있었다.