문제

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

나의 코드

"""

"""

from collections import deque
from sys import stdin

input = stdin.readline

n, m = map(int, input().split())
graph = [ [] for _ in range(n+1) ]

# 무방향 그래프 생성
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# v는 현재 번호, target은 목표로 하는 번호
def bfs(v, target):
    cnt = 0 # cnt는 v -> target으로 가는 단계 수
    q = deque([(v, cnt)])

    visited = [False] * (n+1)
    visited[v] = True

    while q:
        node, cnt = q.popleft()

        if node == target:
            return cnt

        for i in graph[node]:
            if not visited[i]:
                q.append((i, cnt+1))

answer = 0
max_tmp = 1e9
for i in range(1, n+1): # 1번부터 n번까지, target도 1번부터 n번까지 해서 각각의 단계 수를 기록한다.

    tmp = 0
    for target in range(1, n+1):
        cnt = bfs(i, target)
        tmp += cnt

    if max_tmp > tmp: # 1번부터 n번까지 각각의 번호에서 단계수를 더한 값을 비교하여 번호를 기록한다.
        max_tmp = tmp
        answer = i # 단계 수가 가장 적은 번호를 입력한다.
        """ (문제 조건에 "케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다." 
        라는 조건이 있지만 for문이 1번부터 n번까지 작은 숫자부터 돌고 있으므로 if 조건을 '>' 으로 둔 다면 사람이 여러명이더라도 
        번호가 가장 작은 사람이 answer에 저장될 것이다. """
        
print(answer)
    

설명

문제 설명 그대로 코드를 구현하면 쉽게 풀 수 있다.
자세한 내용은 주석에 달아 놓음.

참고 자료