케빈 베이컨의 6단계 법칙 (1) 썸네일형 리스트형 [BOJ] 백준 1389 케빈 베이컨의 6단계 법칙 (Swift) 문제https://www.acmicpc.net/problem/1389풀이이 문제를 처음 봤을 때, 간선의 비용이 동일하다는 점. 최단 경로를 구해야 한다는 점에서 BFS 알고리즘을 떠올렸다.BFS의 시간복잡도가 어떻게 될까도 생각해봤다.$O(V + E)$ 라는 점, 최악의 경우 $O(100 + 5000)$ 이 될 것이라고 생각했다.또한 모든 친구($N$)에 대해 검사를 해봐야 하므로, $O(V * (V + E))$ 이지 않을까..?$100 \times 5100$라면 충분히 통과할 것이라고 생각했다.처음엔 다음과 같이 생각했다.1번노드에서 각 노드로 도달하는 depth를 전부 구해 더해줘야겠다라고 생각했다.즉, 1번 -> 2번으로 가능 최소비용 + 1번 -> 3번으로 가능 최소비용.. 이렇게 전부 구해야지.. 이전 1 다음
