DHistory

[Baekjoon] Shortest Path - 1389 케빈 베이컨의 6단계 법칙 본문

Computer Science/Algorithm

[Baekjoon] Shortest Path - 1389 케빈 베이컨의 6단계 법칙

ddu0422 2023. 10. 30. 19:09

문제

 

1389번: 케빈 베이컨의 6단계 법칙

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻

www.acmicpc.net

 

풀이

import sys

INF = 1e9

n, m = map(int, sys.stdin.readline().rstrip().split())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    graph[a][b] = 1
    graph[b][a] = 1

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            graph[i][j] = 0

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

result = 0
max_value = sum(graph[0])

for i in range(1, n + 1):
    if max_value > sum(graph[i]):
        max_value = sum(graph[i])
        result = i

print(result)

 

채점 결과

 

저작자표시

'Computer Science > Algorithm' 카테고리의 다른 글

[Baekjoon] Shortest Path - 15723 n단 논법  (0) 2023.10.31
[Baekjoon] Shortest Path - 1446 지름길  (0) 2023.10.31
[Baekjoon] Shortest Path - 11403 경로 찾기  (0) 2023.10.30
[Baekjoon] Shortest Path - 1058 친구  (0) 2023.10.30
[Baekjoon] Shortest Path - 18352 특정 거리의 도시 찾기  (0) 2023.10.30
'Computer Science/Algorithm' Related Articles more