BFS? Dijkstra?

여느 날처럼 에줍사 스터디를 진행하다가 그래프 탐색 문제에 대해 논의를 하던 중 나머지 스터디원들은 BFS로 접근을 했지만, 혼자 다익스트라로 접근을 했던 적이 있습니다.

 

"왜 다익스트라를 떠올렸을까?"라는 생각을 한 결과, 다음과 같은 잘못된 기저가 깔려있다는 것을 알 수 있었습니다.

1. 시간복잡도 : Dijkstra < BFS < DFS
2. BFS 또한 완전탐색으로 최단 거리를 찾는데 시간이 오래 걸릴 것이라 생각함
3. 알고리즘 특성 차이

이번 회고를 통해 아래와 같이 잘못된 정보들을 바로잡으려합니다.

1. 추상적인 시간복잡도
2. 두 알고리즘의 동작 방식
3. 조건에 따른 수행 방식

 

BFS와 Dijkstra에 대한 정리는 이전에 정리해 두었던 글이 있으니 참조용으로 링크만 올려두겠습니다.

https://infinitecode.tistory.com/13

[알고리즘] 너비 우선 탐색(BFS)

https://infinitecode.tistory.com/19

[알고리즘] 데이크스트라(Dijkstra)

---

BFS는 DFS와 다르게 왜 최단경로를 찾을 수 있을까?

BFS의 경우 시작 정점에서 가까운(인접한) 정점부터 순서대로 탐색합니다.

이는 곧 방문 순서가 최소시간 순서임을 알 수 있는데요.

FIFO 구조의 Queue 자료구조를 사용하는 것에서도 알 수 있습니다.

 

현재 탐색중인 정점에서 모든 인접 정점(동일 레벨)을 차례로 방문합니다.

그 후 다음 레벨로 이동하게 되는데요.

이러한 특성 때문에 현재 탐색중인 레벨보다 낮은 레벨이 후에 나올 수는 없게 됩니다.

-> 현재 좌표(x,y)에 대해 현재 방문한 경로보다 최적의 경로(더 빨리 도착할 수 있는 경로)가 나올 수 없음.

 

또한 BFS는 최단경로임이 보장되기 때문에 다음과 같이 탐색 로직에서 분기 처리를 할 수 있습니다.

if(도착지점에 도달했을 경우)
	return 현재 레벨(시간);

 

DFS의 경우에는 한 경로에 대해 가지 못하게 될 때까지 탐색하고, 그 후 다른 경로를 재탐색합니다.

또한 방향 배열을 어떤 순으로 두는지에 따라 달라지게 됩니다.

예로 [상,하,좌,우] 순으로 탐색하게 될 경우 상에 대해서만 끝까지 탐색하게 되는거죠.

 

이러한 특성 때문에 현재 탐색중인 레벨보다 낮은 레벨이 이후에 나올 수 있게 되므로 처음 도착한 지점이 최단 경로임을 보장하지 못하게 됩니다.

물론 DFS의 첫 탐색 결과가 최단경로일 경우의 수는 있습니다. 그러나 각 좌표에 대해 최단시간을 보장하지 못하기에 모든 경로를 탐색해야 정해를 구할 수 있습니다.

---

어떠한 조건에서?

BFS를 통해 구한 값이 최단경로임을 보장하기 위해서는 다음과 같은 조건이 필요합니다.

1. 가중치가 없는 그래프
2. 모든 간선의 가중치가 동일한 경우

위에서 알아봤듯 BFS는 무조건 인접한 정점으로만 탐색을 진행합니다.

또한 BFS는 한번 방문한 정점에 대해 방문 체크를 진행하기 때문에 두 번 방문하게 되는 경우가 없습니다.

이는 곧 x,y 좌표를 방문 하는 여러 경로에 대해 비교를 진행하지 않는다는 말입니다.

 

가중치는 모두 한 칸에 1로 동일하다는 전제

그렇기 때문에 위 그림 처럼 어떤 "경로"로 왔냐에 따라서 값이 변경되면 안됩니다.

다르게 본다면 BFS는 최단 시간을 찾는다기 보다는 지나온 정점의 개수를 세는 것(혹은 탐색 횟수)으로 봐도 됩니다.

 

만약 다른 가중치를 가지게 된다면 최단 경로라는 명제가 틀릴 수도 있다는 말이죠.

---

다익스트라는 그럼 BFS와 어떻게 다른걸까?

BFS는 "인접 여부", "탐색 횟수"만을 거리로 판단하고 값을 구합니다.

그러나 이것만으로 최단 경로를 구할 수 없는 경우가 있습니다.

바로 각 정점간의 가중치가 다른 경우죠. <아래 그림 참고>

 

제일 처음 방문하는 정점에 따라 값이 변경

BFS의 경우 만약 방향벡터를 오른쪽먼저 탐색하게 된다면 (1,1)은 10이 되고, 아래쪽부터 탐색하게 되면 4가 됩니다.

이처럼 "어떤 경로"로 왔냐에 따라서 값이 바뀔 수 있다면 BFS가 아닌 다익스트라를 사용해야 합니다.

 

다익스트라의 경우 우선순위 큐를 사용해서 이러한 가중치라는 조건을 추가적으로 판단합니다.

현재까지의 "가중치 합"이 최소가 되는 경우를 우선적으로 탐색하는 것이죠.

 

인접 정점 이동 가중치가 다른 경우

위 그림에서 큐에 오른쪽(5)을 먼저 추가했다 하더라도 우선순위 큐에 의해서 아래(3)를 먼저 탐색하게 됩니다.

이처럼 현재 탐색중인 정점들에 대해 '가중치'를 기준으로 탐색 순서를 정하는 것이 다익스트라의 큰 특징 중 하나입니다.

 

한가지 고민해볼만한 부분은 "현재 도착한 좌표(x,y)에 대해서 최단 경로임을 보장할 수 있느냐?" 입니다.

이에 대한 대답으로는 현재 탐색중인 모든 가중치 합에 대해 최소값을 기준으로 탐색 우선순위를 정하기 때문에 보장할 수 있게 됩니다.

---

+ Think

모든 문제를 풀 때 마다 '시간복잡도'를 확실히 계산 해야합니다.

그 다음은 문제에 해당하는 알고리즘을 선택하게 되는데요.

이번처럼 알고리즘의 특성을 모르고 접근을 하게 되는 경우가 있다면 한번쯤 되짚고 넘어가면 좋을 것 같다고 생각 했습니다.

 

확실히 스터디를 하며 사고에 대한 대화를 나누니, '모르고 있다는 걸 몰랐던 부분'들을 알 수 있었습니다.

저의 경우에는 스터디를 하면서 위 내용 외에도 알게 되었던 것들이 있는데요.

1. 시간에 대한 초조함이 생각보다 강함.
2. 생각 나는대로 코드를 먼저 써내려가는 습관
3. 시간복잡도 계산이 추상적.

이후에도 스터디와 이외 시간을 활용해서 점점 더 효율적인 알고리즘 풀이가 가능하도록 노력해야 할 것 같네요!