tmdrjf01   6년 전

dfs 알고리즘과 다익스트라 알고리즘을 공부하는데
제가 만든 똑같은 테스트 케이스(엄청 단순)에선 dfs 알고리즘이 훨씬 실행이 빠르게 되네요.
(dfs 알고리즘이 분명 최단 거리가 안나온다는 보장이 있다는데 그런 테스트케이스는 만들줄 모르겠습니다 ㅠ)
그런데도 불구하고 정확성이 좋아서 다익스트라 알고리즘이 path finding에서 자주 쓰인다고 하는데
dfs 알고리즘과 다익스트라 알고리즘의 차이가 대체 뭐죠?
각각의 정확한 장단점도 가르쳐주시면 감사하겠습니다.

chogahui05   6년 전

알고리즘 특성상. 그렇죠. 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)의 차이라고 볼 수 있겠네요.

chogahui05   6년 전

즉, 가중치가 모두 같은 경우에는.

(그러니까 인접한 정점간의 탐색 비용이 1로 똑같을 때가 BFS, DFS잖아요.)

그냥 BFS나 DFS를 쓰는 게 이득이죠.


다익스트라 같은 경우는..

선분의 가중치가 다른 경우에.. 예를 들어서


1에서 2까지 가는 길의 비용이 3

2에서 4까지 가는 길의 비용이 1

1에서 4까지 가는 비용이 1000000 이라고 했을 때.


이 경우에는 bfs를 돌려버리면 안 됩니다. 만약에 그렇게 한다면 1에서 4까지 방문을 먼저 해 버린담에.

어? 방문했네? 하고 1에서 4까지 가는 최단 거리 = 1000000 이라고 할 텐데.

사실은 4거든요.


즉, 가중치가 모두 다른 경우에 다익스트라를 씁니다. (단, 가중치가 양의 가중치일 때)

tmdrjf01   6년 전

정말 도움이 되었습니다! 감사합니다

용법의 차이를 잘 설명해주셔서 좋네요

댓글을 작성하려면 로그인해야 합니다.