[백준] 2660-회장뽑기 [Python]

문제

2660번: 회장뽑기

---

 

문제 풀이

---

지인들 중 연결고리가 가장 긴 사람을 기준으로 그 길이로 점수를 매기고, 해당 점수가 가장 작은 사람을 회장 선출한다.

 

다익스트라 알고리즘으로 문제를 해결해도 될 것 같지만, 해당 문제의 입력 크기가 50으로 매우 작으므로 단순하게 그래프로 구현하여 bfs로 가장 연결고리가 긴 사람을 구했다.

 

 

 

코드

---

from collections import deque

def bfs(graph,root,members):
    queue = deque([root])
    friend_count = [-1]+[members for _ in range(members)]
    friend_count[root] = 0
    while queue:
        node = queue.popleft()
        for i in graph[node]:
            if friend_count[i] > friend_count[node] + 1:
                friend_count[i] = friend_count[node] + 1
                queue.append(i)
    return max(friend_count)

members = int(input())

graph = {}
for i in range(1,members+1):
    graph[i] = []
a,b = map(int,input().split())

while a!= -1 and b != -1:
    graph[a].append(b)
    graph[b].append(a)
    a,b = map(int,input().split())
    
chairman_list = []
chairman_count = members
for i in graph.keys():
    tmp = bfs(graph,i,members)
    if tmp < chairman_count:
        chairman_count= tmp
        chairman_list = [i]
    elif tmp == chairman_count:
        chairman_list.append(i)
chairman_list.sort()
print("{} {}".format(chairman_count,len(chairman_list)))
print(*chairman_list)

 

friend_count라는 리스트를 가능한 수 중 최댓값보다 큰 멤버의 수로 초기화하고,

루트 노드는 0으로 초기화한다.

 

로직은 다음과 같다.

-1) 현재 살피고 있는 노드와 연결된 친구들 중, friend_count 값이 현재 살피고 있는 노드의 friend_count + 1 보다 큰 경우, 

해당 노드는 개선의 여지가 있으므로 friend_count[i] 를 friend_count[node] + 1로 바꿔준 뒤, queue에 집어넣고 반복.

 

-2) 크지 않은 경우, 해당 노드는 현재 상태에서 최선의 값을 갖고 있으므로 아무 일도 하지 않는다.

 

while문을 빠져나오면, 모든 노드들이 최선의 값들을 갖고 있을 것이므로 우리가 관심 있어할 max(friend_count) 값을 리턴해 준다.

 

 

글을 서술하면서 bfs 보단 Bellman-Ford 알고리즘과 비슷하다고 느꼈다.

 

그 이유는 bfs는 한번 방문하면 이후 방문을 하지 않는데, 값이 갱신될 때 마다 몇번이고 다시 방문하기 때문이다.