알고리즘 특성상. 그렇죠. dfs나 bfs는
맵이 R*C라고 하면 R*C임이 보장이 되거든요.
그런데 다익스트라 같은 경우 잘 생각해 보면
한 녀석당 인접한 정점이 4개에서 8개잖아요. (대각선이 포함된다면)
그러면 O((E+V)logV) 정도의 복잡도를 가지게 되는데요.
Edge 수 = 선분의 수
Vertex 수 = 노드의 수
이 정도 될 텐데요. 일단 Vertex의 수가 RC
Edge 수가 4RC ~ 8RC 즈음 되네요.
이걸 (E+V)logV에 넣어볼까요?
5RC*log(RC)
RC = N으로 치환하면
O(N)과 O(NlogN)의 차이라고 볼 수 있겠네요.
tmdrjf01 6년 전 1