99클럽 코테 스터디 2일차 TIL: 최단 경로

문제

풀이

이 문제를 처음 봤을 때, 간선의 비용이 동일하다는 점. 최단 경로를 구해야 한다는 점에서 BFS 알고리즘을 떠올렸다.
BFS의 시간복잡도가 어떻게 될까도 생각해봤다.
$O(V + E)$ 라는 점, 최악의 경우 $O(100 + 5000)$ 이 될 것이라고 생각했다.

또한 모든 친구($N$)에 대해 검사를 해봐야 하므로, $O(V * (V + E))$ 이지 않을까..?
$100 \times 5100$라면 충분히 통과할 것이라고 생각했다.

처음엔 다음과 같이 생각했다.
1번노드에서 각 노드로 도달하는 depth를 전부 구해 더해줘야겠다라고 생각했다.
즉, 1번 -> 2번으로 가능 최소비용 + 1번 -> 3번으로 가능 최소비용.. 이렇게 전부 구해야지 하고 생각하면서
bfs를 1번에서 특정 노드 까지의 비용을 모두 실행시켜야겠다고 생각했다.

문제를 천천히 다시 읽어보며 다시생각해봤다.
이 문제에는 "모든 사람은 친구 관계로 연결되어져 있다." 라는 조건이 있다.
이 말은 즉, 1번 노드에서 모든 노드로 도달이 가능하다는 점이다.
1번노드에 대해 BFS를 실행해 모든 depth를 더하면 그것이 케빈베이컨지수가 될 수 있다.

그래서 BFS를 실행하면서, Queue에서 노드를 꺼내고 다음 노드는 해당 노드의 depth+1로 설정하여 Queue에 담아주는 작업을 진행했다.
코드는 다음과 같으며 거의 BFS 기초와 동일하다.

추가로 전날 플로이드-워셜 알고리즘을 통해 문제풀이한 것이 떠올라서 해당 알고리즘을 사용하여 풀이할 수 있지 않을까도 싶었다.
플로이드-워셜 알고리즘은 시간복잡도가 $O(n^3)$이며 n이 100으로 아주 작은 수기 때문에 시간내에 풀 수 있다고 느꼈다.

여기서 BFS로 푼 방식은 러프하게 계산해봤을 때 최악의 경우 연산이 다음과 같을 것이라고 생각했다.
$O(100 * 5100) = (510,000)$

플로이드 워셜의 경우는?
$O(100 * 100 * 100) = 100,000)$

여기서 플로이드 워셜의 경우 24번째줄 for문이 한 번 더 추가되니깐.. $O(n^3) + O(n)$ 정도가 될 것 같다.
물론 시간복잡도에서 낮은 차수에 대해서는 별로 신경을 쓰진 않지만.. ㅎ 굳이 따지자면..

그래서 백준에서 두 풀이방법으로 진행했을 때, BFS가 좀 더 빠른 것이지 않을까..?

후기

문제를 보자마자 BFS를 떠올렸는데, 이는 개인적으로 BFS를 플로이드-워셜보다 많이 풀어보고 익숙해서 그렇지 않았을까.. 라는 생각이 든다.
그리고 BFS, DFS의 시간복잡도는 언제나 헷갈려서 곰곰히 생각해야 떠올랐다..