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

그래프, bfs / 골드 5

🤴🏻

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

2660번: 회장뽑기

 

 

내 풀이

from collections import deque

def bfs(s):
    visited[s] = True
    
    q = deque()
    q.append(s)

    while q:
        c = q.popleft()
        for k in member[c]:
            if not visited[k]:
                visited[k] = True
                score[k] = score[c] + 1
                q.append(k)

    final_score.append(max(score))


N = int(input())
member = [[] for _ in range(N+1)]
final_score = []

while True:
    m1, m2 = map(int, input().split())
    if m1 == -1 and m2 == -1:
        break
    member[m1].append(m2)
    member[m2].append(m1)

for i in range(1, N+1):
    visited = [False] * (N+1)
    score = [0] * (N+1)
    bfs(i)

leader_score = min(final_score) # 회장 후보의 점수
print(leader_score, final_score.count(leader_score))
for i in range(len(final_score)):
    if final_score[i] == leader_score:
        print(i+1, end=' ')

bfs(너비 우선 탐색)으로 풀었다.

 

 

코드 설명

 

member: 회원별로 친구 사이인 회원의 번호들을 저장하는 이차원 리스트.

final_score: 회원별 최종 점수를 저장하는 리스트

member = [[] for _ in range(N+1)]
final_score = []

 

모든 회원의 점수를 계산한다.

bfs 호출 전, visited(방문한 회원인지 아닌지를 구별하는 리스트)와 score(회원 점수를 저장하는 리스트)를 초기화해 준다.

for i in range(1, N+1):
    visited = [False] * (N+1)
    score = [0] * (N+1)
    bfs(i)

 

최종 점수(final_score) 중, 가장 작은 점수가 회장 후보의 점수가 된다.

leader_score = min(final_score) # 회장 후보의 점수
print(leader_score, final_score.count(leader_score))
for i in range(len(final_score)):
    if final_score[i] == leader_score:
        print(i+1, end=' ')

 

 

✔️ bfs 함수 내

 

현재 회원과 친구 사이인 회원들을 모두 검사하며, 아직 방문하지 않은 회원이라면 점수를 증가시킨다.

final_score에는 가장 큰 값(해당 회원의 최종 점수)을 추가한다.

while q:
    c = q.popleft()
    for k in member[c]:
        if not visited[k]:
            visited[k] = True
            score[k] = score[c] + 1
            q.append(k)

final_score.append(max(score))