[BOJ/python] 2660: 회장뽑기

문제

✔️ gold 5
그래프 이론
그래프 탐색
너비 우선 탐색
최단 경로
플로이드–워셜

문제 흐름

두가지 방법으로 풀었다.
처음 보고는 그냥 모든 노드에 대해서 BFS를 통해 순회해서 점수를 계산하고 최저점수를 찾으면 되겠다 생각했는데,
보다보니 최근에 새로 공부한 알고리즘인 플로이드-워셜 알고리즘을 적용해도 괜찮겠다는 생각이 들었다.
두 방법 모두 공통적으로 계산한 값들을 비교하면서 최저값과 그 값을 가진 노드의 번호를 찾도록 했다.

코드

# 회장뽑기 
# graph


### floyd-warshall
import sys
import pprint
input = sys.stdin.readline

def fw(g: list):
    n = len(g)
    for k in range(n):
        for a in range(n):
            for b in range(a+1, n):
                g[a][b] = min(g[a][b], g[a][k]+g[k][b])
                g[b][a] = g[a][b]

if __name__ == "__main__":
    n = int(input())
    g = [ [float('inf') for i in range(n+1)] for j in range(n+1)]
    while 1:
        u, v = map(int, input().split())
        if u == -1 and v == -1:
            break
        g[u][v] = 1
        g[v][u] = 1
    
    # pprint.pprint(g)
    fw(g)
    # pprint.pprint(g)

    min_val = float('inf')
    res = []
    for i in range(1, n+1):
        g[i][i] = 0
        tmp = max(g[i][1:])
        if tmp < min_val:
            min_val = tmp
            res = [i]
        elif tmp == min_val:
            res.append(i)
    
    print(min_val, len(res))
    print(*sorted(res))

# 회장뽑기 
# graph


### bfs
import sys
import pprint
from collections import deque
input = sys.stdin.readline

def bfs(g: list, s: int):
    res = 0
    q = deque([(s, res)])
    n = len(g)
    vst = {node: 0 for node in range(1, n+1)}
    vst[s] = 1

    while q:
        x, d = q.popleft()
        for n in g[x]:
            if vst[n]:
                continue
            q.append((n, d+1))
            if res < d+1:
                res = d+1
            vst[n] = 1
    return res
    

if __name__ == "__main__":
    n = int(input())
    g = {node: [] for node in range(1, n+1)}
    while 1:
        u, v = map(int, input().split())
        if u == -1 and v == -1:
            break
        g[u].append(v)
        g[v].append(u)
    
    min_val = float('inf')
    res = []
    for i in range(1, n+1):
        tmp = bfs(g, i)
        if tmp < min_val:
            min_val = tmp
            res = [i]
        elif tmp == min_val:
            res.append(i)
    
    print(min_val, len(res))
    print(*sorted(res))

마무리

최근 배운 알고리즘을 다시 사용해 볼 수 있는 기회여서 좋았다.
두가지 방법으로 풀었지만 두 방법에 큰 효율 차이는 없었다.
해당 문제에서는 회원의 수가 50이라 작아서 괜찮았지만 아무래도 플로이드-워셜 알고리즘은 시간복잡도가 크기 때문에 노드 수가 더 커질 경우 효율이 안좋아질 가능성이 있을 것 같다.