목록1389 (1)

-

floyd warshall :: 백준 :: 케빈 베이컨의 6단계 법칙 :: 1389

케빈 베이컨의 6단계 법칙 1389https://www.acmicpc.net/problem/1389 [풀이 방법]이 문제 역시 dfs, bfs, 플로이드 와샬 알고리즘 등 다양한 방법으로 풀 수 있다.난 플로이드 와샬 알고리즘으로 풀어봐야지... 가장 간단한 방법인 것 같다. 1. 첫째 줄에 N과 K를 입력받는다. N은 정점, K는 간선의 수라고 생각했다. 2. relation이라는 N+1 X N+1 행렬을 생성 후 이후에 나오는 간선 정보들을 저장했다. 여기서, 1이 3을 알때 3도 1을 안다고 볼 수 있으므로 relation[1][3] = 1 relation[3][1] = 1 을 해준다. 3. 탐색을 시작한다.relation[r][k] != 0이고 relation[k][c] != 0 일때 -relat..
알고리즘/탐색 2016. 11. 3. 14:01
Prev 1 Next