[백준] 1753 최단경로 [다익스트라와 BFS차이를 한번 생각해보자 + 코드 없음]

다익스트라(dijkstra)

https://www.acmicpc.net/source/64016802

로그인

 

설명

 이번 포스팅 내용은 코드가 들어 있지 않습니다. 해당 문제에 대한 코드는 다익스트라의 기본적인 코드 내용이기 때문에 올리지 않고 다익스트라와 BFS의 차이가 무엇인지 둘 다 최단경로를 찾기 위해 사용되는 알고리즘인데 목적이 어떻게 다른지에 대해서 중점적으로 공부한 내용을 작성하겠습니다.

 

 다익스트라(dijkstra) 알고리즘은 최단경로를 찾기 위해 사용되는 알고리즘이다. 이 알고리즘의 특징이라고 본다면 '가중치'가 있는 그래프에서 사용되는 특징을 가지고 있다. 앞서 이전 포스팅에서는 BFS를 활용해서 최단경로를 찾는 문제들을 접해봤었고, 왜 DFS 보다 BFS를 최단경로에 사용되는지 알아보았다. 그렇다면 다익스트라도 최단경로를 찾기 위해서 사용되는데 BFS와 차이점이 무엇일까?

 

 우선 BFS 같은 경우 너비 우선 탐색 이라고 많이 알고 있다. 즉 너비를 우선적으로 탐색해 나가면서 가장 먼저 도착하는 경로가 무엇이냐를 묻고 있는 것이다. 그때 그 경로가 얼마큼 다른 경로를 걸어오면서 혹은 지나오면서 도착하게 되었느냐를 물어보는 것이 BFS를 사용해서 최단경로를 찾는 목적이라고 말할 수 있을 것 같다. 그렇다면 다익스트라 같은 경우는 가장 먼저 도착하는 게 아닌 것인가. 둘의 명확한 차이는 아래 문장으로 정리해보고자 한다.

 

 

BFS는 최단 이동 거리 혹은 이동횟수를 목적으로 한다.

다익스트라는 비용을 고려하여 가장 빠른 길을 찾는 것을 목적으로 한다.

 

 

 위 문장을 토대로 한가지 예시를 들어보려고 한다. 만약 BFS가 찾은 경로가 즉 가장 빨리 도착한 경로가 1-2-3-6이라는 비용을 거쳐온 경로라고 가정해 보자. BFS는 가장 빠른 경로, 가장 적은 횟수로 방문했을 때의 이동 횟수를 저장해서 찾은 경로라고 가정해 본다면 비용을 계산해 봤을 때 1+2+3+6 = 12 만큼의 비용, 돈, 시간 등으로 표현될 수 있다. 그랬을 때 생각해 볼 수 있는 것은 BFS가 과연 비용을 고려해서 최단경로를 찾은 것인가? 분명 BFS의 목적은 가장 빠른 이동 경로를 찾는데 목적을 두고 있다. 그렇다는 건 따로 비용을 처리하지 않았다면 비용을 고려하지 않았다고 볼 수 있다. 그렇기 때문에 BFS가 찾은 경로가 항상 빠른 경로(최단경로)를 보장하지만 그렇다고 그 경로가 비용을 고려했을 때 최적의 경로는 아니라는 것이다.

 

 다익스트라 알고리즘으로 똑같은 그래프에서 경로를 찾았다고 가정해 보자. 이때는 다익스트라 알고리즘은 '가중치'를 고려해서 찾은 최단경로라고 가정한다. 그랬을 때 BFS가 찾은 경로가 1-1-1-2-3 = 8의 비용을 가진 경로라고 해본다면 최단경로가 다르다는 것을 알 수 있다. 결국 그렇다는 건 BFS와 다익스트라의 최단경로는 어떤 기준을 두고 최단경로를 찾는지가 BFS와 다익스트라의 차이라고 볼 수 있다. 예시 그대로 분명 더 많은 길을 탐색해 오면서 도착한 길임에도 불구하고 비용은 가장 적다. BFS는 비용이 큰 곳을 탐색해 오면서도 가장 먼저 도착한 길이다. 그렇다는 건 둘의 기준이 다르다는 것을 알 수 있고 그때의 기준이라는 것은 '비용 혹은 가중치'를 고려해서 탐색을 하는지 아니면 '빠른 경로를 찾는 것'을 목적으로 두는지에 따라 다르다고 볼 수 있다. 기준을 다르게 하고 있기 때문에 추구하는 목적이 달라진다. 현실세계에서 비유를 간략하게 해 보자면 아래와 같다.

 

 

1. 나는 그냥 빠르게 도착해볼래 뭐하러 비용을 고려해서가

2. 나는 빠르게 도착하는것도 좋지만 힘을 너무 많이 들여서 가긴 싫어

최소한의 힘만 사용해서 가보는 길을 가고 싶어.

 

 

 

 위 문장으로 둘의 선택은 각자의 다른 기준을 가지고 추구하는 목표가 달라졌다. 이는 곧 기준이 다르기 때문에 서로를 동등한 위치에서 비교할 수 없다는 뜻이다. 만약 서로가 같은 기준을 가지고 있을 때라면 어떤 길이 효율적인지 비교해 볼 수 있겠지만 (BFS와 DFS처럼) 서로 다른 기준을 가진 것끼리 비교한다는 것은 공통된 목적 최단경로를 찾는 것에 더해서 (비용을 고려하여, 빠르게만 도착하여)와 같은 접미사를 붙여 의미를 다르게 만들기 때문에 결국 하나의 다른 목적으로 완성되어 동등한 위치에서 비교가 어려워진다. 이게 조금 이해가 안 된다면 서로 달리기를 100m 하기로 했을 때 나는 두 다리 다 써서 도착지까지 빠르게 갈래와 한 다리만 써서 갈래는 서로 어떻게 달려 나가는지에 대한 방법자체가 다르다. 두 다리 써서 가보는 사람은 두 다리를 써서 가보는 방법만을 선택해서 목적지까지 도착하게 될 것이고, 한 다리만 쓰는 사람은 한 다리만 썼을 때의 방법만 선택해서 목적지까지 도달할 것이기 때문에 결국 어떠한 방법 혹은 기준을 갖는지에 따라 하나의 목적은 같더라도 최종 목적의 결과는 다를 수 있다.

 

 이해를 위한 예시가 적절했는지는 잘 모르겠다. 하지만 분명한 건 BFS와 다익스트라는 둘이 찾는 최단경로의 방법과 기준이 다르다는 것이다. 그래서 보통 알고리즘에서 최단경로를 찾을 때 비가중치 그래프와 가중치 그래프로 나눠서 생각한다. 비가중치라는 건 말 그대로 가중치가 없다. 혹은 정의되지 않아서 모두 같다.라고 보고 문제에 접근을 하게 된다. 그렇다는 건 A->B로 가는 비용이나 B->A로 가는 비용이나 같다는 의미가 되며 그 어떤 간선으로 이루어진 곳도 전부 가중치가 같다. 혹은 없다. 그렇다면 비용을 고려했을때 최단경로를 찾는 것 자체가 불가능하다. 따라서 비가중치 그래프에서 비용을 고려한다는 건 말이 되지 않는다. 그렇기 때문에 위에서 BFS가 찾은 경로예시를 들었던  것에서 가중치를 고려해서 찾은 경로는 사실 가중치를 고려한 것이 아닌 최단 이동경로일 뿐이다. 반면에 가중치 그래프 같은 경우 가중치 혹은 힘, 시간, 비용 등으로 불리는 어떠한 기준이 존재하고 그 기준들을 가지고 최대 혹은 최소의 힘, 시간 등을 들여서 도착하는 경로를 찾고자 할 때 다익스트라를 사용한다고 볼 수 있다. 따라서 둘의 목적 자체가 다르며 어떠한 상황에서 써야 하는지 명확한 차이를 느껴볼 수 있을 것 같다.

 

 

혹시라도 애매한 부분이 있거나 잘못된 부분이 있어서 지적해주신다면 수정하겠습니다.)