[백준 2660번] 회장뽑기

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

import sys
from collections import deque

input = sys.stdin.readline

# 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다
# 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.

# 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점
# 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구
# 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구

# 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이

# 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램

n = int(input())

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

minimum = float("inf")

lists = []

while True:
    a, b = map(int,input().split())

    if a == -1 and b == -1:
        break

    graph[a].append(b)
    graph[b].append(a)

def bfs(index):

    visited = [False]*(n+1)
    visited[0] = True
    
    q = deque([(index,0)])

    score = 0

    visited[index] = True

    while q:

        v, depth = q.popleft()

        score = depth
        
        for next in graph[v]:
            
            if not visited[next]:
                visited[next] = True
                q.append((next,depth+1))

    if all(visited):
        return score
    else:
        return -1
    
for i in range(1,n+1):
    result = bfs(i)

    if result != -1:
        if result < minimum:
            minimum = result
            lists = []
            lists.append(i)
            
        elif result == minimum:
            lists.append(i)
    
print(f"{minimum} {len(lists)}")

for i in lists:
    print(i,end=" ")

 

이번 문제는 각 회원마다 다른 회원들과의 연결 관계에 따라 점수가 부여된다고 가정했을 때, '가장 점수가 낮은 사람의 점수와 명수', 그리고 '점수가 가장 낮은 회원번호들'을 모두 출력하는 문제이다.

 

문제의 조건에 따르면 모든 회원과 친구인 경우에 1점이고 친구 관계가 한 단계씩 거쳐갈 때마다 1점씩 늘어간다고 되어있다.

 

따라서 특정 지점으로부터 다른 지점까지의 깊이(단계)를 저장하며 탐색할 수 있는 BFS알고리즘을 선택하였다.

 

그 후 모든 회원과 친구인 경우 즉, 모든 방문이 완료되었을 때(all(visited)) 점수를 반환하고 방문하지 못한 노드가 존재한다는 것은 점수를 얻을 수 없다는 의미이므로 -1을 반환해주었다.

 

BFS알고리즘을 복습해볼 수 있었던 문제였다 :)