[백준][BFS/플로이드워셜] 2660. 회장뽑기

2660. 회장뽑기

2660번: 회장뽑기

 

• 내 풀이
  • bfs
  • 처음에 1~n+1을 시작점으로 해서 한번씩 다 돌아야 하는 걸 이차원배열로 만들다가 헷갈렸다
  • 이렇게 while문 안에 for문이 2번 돌 것 같은 경우에는
    • for 문 하나를 밖으로 빼버리고, for문으로 bfs를 실행하자
    • 그럼 visited가 1차원 배열이 될 수 있음

# 1점: 모두가 친구
# 2점: 모두가 친구 / 모두가 친구의 친구
# 3점: 모두가 친구/ 친구의 친구/ 친구의 친구의 친구
# 점수가 가장 낮은 사람
from collections import deque


def bfs(start):
    queue = deque()
    queue.append(start)
    visited = [-1 for j in range(n+1)]
    visited[start] = 0

    while queue:
        q = queue.popleft()

        for x in tree[q]:
            if visited[x] != -1:
                continue
            visited[x] = visited[q]+1
            queue.append(x)

    result[start] = max(visited)


n = int(input())
tree = [[] for _ in range(n+1)]
while True:
    f1, f2 = map(int, input().split())

    if f1 == -1 and f2 == -1:
        break
    tree[f1].append(f2)
    tree[f2].append(f1)

result = [0 for _ in range(n+1)]
for i in range(1, n+1):
    bfs(i)

score = min(result[1:])
top = [i for i in range(1, n+1) if result[i] == score]
print(score, len(top))
print(*top)