[백준] 1389번 파이썬

난이도 SIVER I

문제링크 : https://www.acmicpc.net/problem/1389

문제해결 아이디어

• 1번 부터 n번까지 순회 하는 반복문을 생성한다.
• 반복문안에서 매번 새로운 visited 배열을 만든다.
• visited 배열에는 해당 인덱스의 번호의 사람이 몇번째로 만나는지 기록한다.
• 이미 방문한 visited 인덱스는 방문하지 않는다.

import sys
from collections import deque


input = sys.stdin.readline

n,m = map(int, input().split())

arr = [[] for _ in range(n+1)]

for _ in range(m):
    a,b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)

# visited = [0] * (n+1) 로 초기화 하고
# 1번부터 n번까지 순회하면서 만나는 숫자를 visited에 기록한다.
# visited의 합 == 케빈 베이컨


answer = [0] * (n+1) # 인덱스 별 베이컨수
answer[0] = int(1e9)
for i in range(1,n+1):
    q = deque()
    visited = [0] * (n+1)
    visited[i] = 1
    cnt = 0    
    q.append(i)

    while q:
        x = q.popleft()

        for k in arr[x]:
            if not visited[k]:
                visited[k] = visited[x] + 1 # 이전 방문횟수 + 1
                q.append(k)

    answer[i] = sum(visited) 



print(answer.index(min(answer)))