kingsubin

• 최소 거리랑 그래프 보고 BFS 생각함.
• V, E 갯수 제한 보고 인접 리스트 생각함.
• search 함수에서 전부 방문했으면 안 돌아도 되는거 처리 할 수 있는거 같은데 시간 문제 없어서 넘어감.
• 문법 헷갈려서 아직 콘솔 안 찍어보면 삐걱거림.
• 풀이 너무 오래 걸림.

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
board = [[] for _ in range(N + 1)]

for _ in range(M):
    x, y = map(int, input().split())
    board[x].append(y)
    board[y].append(x)

def search(x):
    dq = deque()
    check = [False] * (N + 1)
    check[x] = True
    total = 0

    for i, v in enumerate(board[x]):
        dq.append((v, 1))

    while dq:
        pop = dq.popleft()
        num = pop[0]
        d = pop[1]

        if not check[num]:
            check[num] = True
            total += d

            for j in board[num]:
                if not check[j]:
                    dq.append((j, d + 1))

    return total

count = [0 for _ in range(N + 1)]
for i in range(1, N + 1):
    count[i] = search(i)

print(count.index(min(count[1:])))

 

---

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