1613 역사

DFS 혹은 플로이드로 문제를 해결할 수 있다.

하나의 케이스에 대해서 구한다면 플로이드의 시간복잡도는 O(V^3)으로 DFS의 시간복잡도(O(V+E))에 비해 굉장히 비효율적이다. 하지만 여러 케이스에 대해서는 케이스마다 다시 실행하지 않고, 한 번 구해놓은 것으로 호출하면서 각 케이스의 답은 O(1)으로 구할 수 있다. 그런데 DFS로 구한다면 O((V+E)*S)가 되버린다

 

따라서 역사 문제는 DFS로 푼다면 O(50000^2)으로 시간 안에 풀 수 없게 된다

 

문제: https://www.acmicpc.net/problem/1238

https://github.com/surinoel/boj/blob/master/1613.cpp

 

시간초과 DFS 소스코드: https://github.com/surinoel/boj/blob/master/1613_dfs_time_excess.cpp