BOJ 백준 2660: 회장뽑기

Table of contents

들어가며

걸린 시간: 24분

사실 처음에 문제를 읽었을 때 무슨 말인지 잘 이해가 안 갔습니다.
그럴 때에는 억지로 문제를 이해하려 들지 말고, 주어진 input값을 직접 simulation하면 잘 이해가 되는 거 같더라고요.

접근

결국 문제의 핵심은 그래프 탐색을 몇 번만에 다 할 수 있냐를 각 노드마다 시작점으로 줘서 구하는 것이었어요.
다행히 N은 최대 50이어서, 어렵지 않게 모든 노드에 대해 각각 1번씩 BFS를 해주어서 쉽게 답을 구해낼 수 있었답니다.

구현

import sys
input = sys.stdin.readline
from collections import deque

def BFS(start):
    distance[start] = 1
    q = deque()
    q.append(start)

    while q:
        cur_node = q.popleft()
        for next_node in graph[cur_node]:
            if distance[next_node] > 0:
                continue
            distance[next_node] = distance[cur_node] + 1
            q.append(next_node)


if __name__ == "__main__":
    N = int(input().strip())
    graph = [[] for _ in range(N + 1)]
    distance = [0 for _ in range(N + 1)]
    ansList = []
    minStepsToTraverseAllNodes = int(1e9)
    while True:
        u, v = map(int, input().strip().split())
        if u == -1 and v == -1:
            break
        graph[u].append(v)
        graph[v].append(u)
    for start_node in range(1, N + 1):
        BFS(start_node)
        stepsToTraverseAllNodes = max(distance) - 1
        minStepsToTraverseAllNodes = min(minStepsToTraverseAllNodes, stepsToTraverseAllNodes)
        ansList.append((start_node, stepsToTraverseAllNodes))
        distance = [0 for _ in range(N + 1)]

    ansList = [*map(lambda x: x[0], filter(lambda x: x[1] == minStepsToTraverseAllNodes, ansList))]
    print(minStepsToTraverseAllNodes, len(ansList))
    print(" ".join(map(str, ansList)))
    # N이 0, 1일 때는 처리를 안 해줘도 되나..?

filter, map 함수를 적극 이용해 봤습니다. (코드를 줄이기 위해서…?!)