[다익스트라/플로이드워셜] (백준_2660) 회장뽑기 - 파이썬

✅ 이문제 처음 접근할 때

친구-친구(2점) -> G[a][b]==G[b][c] ; O(n^3)
...
친구-친구-친구-친구-친구-친구(5점) -> G[a][b]==G[b][c]==G[c][d]==G[d][e]==G[e][f] ; O(n^6)
이렇게 생각해서 뭐야 플로이드워셜로 풀면 시간 오류 뜨겠는데 생각해서 1) 다익스트라를 N번 돌려서 풀었는데 ,

2) 플로이드워셜을 DP랑 같이 사용해서 풀 수도 있는 문제였다.

 

✅ 처음 다익스트라로 풀때 실수했던 부분:

처음 시작점을 지나고 나서 
distance[start][nv] = nd
distance[nv][start] = nd -> 이부분까지 갱신을 해줬는데 그러면 안된다.
왜냐면 Dijkstra의 알고리즘에서 거리는 특정 시작 노드에서 다른 노드까지 한 방향으로만 계산된다.

정확히 말하면 시작노드가 다르므로 계산의 오류가 생긴다.(각 방향 독립적이다)

메모리-시간 비교

 

✅  다익스트라 코드

from heapq import heappop,heappush
N = int(input())
G = [[] for _ in range(N+1)]
INF = int(1e9)
while True:
    a,b = map(int,input().split())
    if a == -1 and b == -1:
        break
    G[a].append((b,1))
    G[b].append((a,1))

distance = [ [INF]*(N+1) for _ in range(N+1) ]

candidate = []

def dijkstra(start):
    q = []
    heappush(q,(0,start))
    distance[start][start]=0
    while q:
        d,v = heappop(q)
        if distance[start][v] < d:
            continue
        for nv,nw in G[v]:
            nd = d+nw
            if nd < distance[start][nv]:
                distance[start][nv] = nd
                heappush(q,(nd,nv))
    heappush(candidate,(max(distance[start][1:]),start))

for i in range(1,N+1):
    dijkstra(i)

first_score,first_hubo = heappop(candidate)
cnt = 1
hubo_list = [first_hubo]

while candidate and candidate[0][0]==first_score:
    score,hubo= heappop(candidate)
    cnt+=1
    hubo_list.append(hubo)

hubo_list.sort()
print(first_score,len(hubo_list))
print(" ".join(map(str,hubo_list)))

✅  플로이드 워셜 코드

N = int(input())
INF = int(1e9)
dp = [[INF]*(N+1) for _ in range(N+1)]

while True:
    a, b = map(int, input().split())
    if a == -1 and b == -1 : break
    dp[a][b] = 1
    dp[b][a] = 1

for i in range(1,N+1):
    dp[i][i] = 0

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if i==j: continue
            elif dp[i][j] > dp[i][k] + dp[k][j]:
                dp[i][j] = dp[i][k] + dp[k][j]
A = []
for i in range(1,N+1):
    A.append(max(dp[i][1:]))
m = min(A)
print(m, A.count(m))
for i, v in enumerate(A):
    if v == m:
        print(i+1, end=' ')