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

🥚문제

---

🥚입력/출력

---

🍳코드(Floyd-Warshall)

INF = int(1e9)

n, m = map(int, input().split())
matrix = [[INF]*(n+1) for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    matrix[a][b] = matrix[b][a] = 1

# 플로이드 워셜 알고리즘
# 자기 자신으로 갈 수 없음, 0
for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            matrix[a][b] = matrix[b][a] = 0
# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            matrix[a][b] = min(matrix[a][b], matrix[a][k] + matrix[k][b])
'''
# 수행된 결과 출력
for a in range(1, n+1):
    for b in range(1, n+1):
        if matrix[a][b] == INF:
            print("INF", end= " ")
        else:
            print(matrix[a][b], end=" ")
    print()
'''
# 케빈 베이컨의 수 구하기
kevinBacon = []
for i in range(1, n+1):
    summation = 0
    for j in matrix[i]:
        if j == INF:
            continue
        else:
            summation += j
    kevinBacon.append([summation, i])
kevinBacon.sort(key=lambda x:[x[0], x[1]])
print(kevinBacon[0][1])

---

🧂아이디어

• 'Floyd-Warshall' 알고리즘

• BFS로 모든 경우에 대해 돌려줘도 답이 나온다고 한다.