063 케빈 베이컨의 6단계 법칙

첫번째 코드

 

그래프에서 최단 거리를 표현하는 방법들을 정리한 후

플로이드-워셜을 이용해야 하는 문제를 풀었다.

 

그래서 코드를 적으면서 비교적 이해가 쉬웠다.

플로이드-워셜 개념을 알고 있다면 문제에 적용하는 방법만 잘 생각하면 쭉쭉 적을 수 있을 것 같다.

(수학적 원리는 아는데 문제에 적용이 걱정 되는 느낌)

 

코드는 책을 참고했다!

코드와 익숙해지자!!

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
distance = [[sys.maxsize for j in range(n+1)] for i in range(n+1)]

for i in range(1, n+1):
    distance[i][i] = 0
    
for i in range(m):
    s, e = map(int, input().split())
    distance[s][e] = 1
    distance[e][s] = 1    

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if distance[i][j] > distance[i][k] + distance[k][j]:
                distance[i][j] = distance[i][k] + distance[k][j]
                
Min = sys.maxsize
answer = -1

for i in range(1, n+1):
    tmp = 0
    for j in range(1, n+1):
        tmp += distance[i][j]
    if Min > tmp:
        Min = tmp
        answer = i
            
print(answer)

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/1389.%E2%80%85%EC%BC%80%EB%B9%88%E2%80%85%EB%B2%A0%EC%9D%B4%EC%BB%A8%EC%9D%98%E2%80%856%EB%8B%A8%EA%B3%84%E2%80%85%EB%B2%95%EC%B9%99

programmers/백준/Silver/1389. 케빈 베이컨의 6단계 법칙 at main · ornni/programmers