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

 

www.acmicpc.net/problem/1389

---

BFS, 플로이드-와샬 등 다양한 형태로 해결할 수 있습니다.

저는 플로이드로 해결했습니다.

 

"dist[i][j] = i와 j가 연결되어 있는 거리"로 정의합니다.

 

초기값은 dist[i][j]= ∞로 두고, 입력이 주어져 있는 경우만 dist[i][j] = 1로 셋팅을 합니다.

 

그 다음에 플로이드를 돌면서

dist[i][j] > dist[i][mid] + dist[mid][j] 이면

dist[i][j] = dist[i][mid] + dist[mid][j] 로 갱신하면 됩니다.

---

코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1389.cc