[백준 2660] 회장 뽑기- python (solved.ac - 골드 5)

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

2660번: 회장뽑기

풀이

문제를 보았을때 알수있는 힌트

친구와 친구 등으로 연결되어있는 것으로 보아 그래프 문제라고 생각들며 이미 들린 곳은 다시 들리지 않게 하면 될듯하다. 또한 BFS를 통해서 총 몇번을 안으로 들어가는지 확인하면 쉽게 풀릴 수 있는 문제이다.

 

import sys
from  collections import deque

input = sys.stdin.readline

n = int(input())

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

while True:
    x,y= map(int,input().split())
    if x==-1 and y == -1:
        break
    graph[x].add(y)
    graph[y].add(x)
result=[]
for j in range(1,n+1):
    queue= deque()
    visited=[False for _ in range(n+1)]
    for i in graph[j]:
        queue.append([i,0])
    visited[j]=True
    count=0
    while queue:
        v= queue.popleft()
        if visited[v[0]]==False:
            visited[v[0]]=True
            for i in graph[v[0]]:
                queue.append([i,v[1]+1])
        if count<v[1]:
            count=v[1]
    result.append(count)
result_min=min(result)
print(result_min,result.count(result_min))
for i in range(n):
    if result[i]==result_min:
        print(i+1,end=" ")

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon2660.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리