BFS - 너비우선탐색

오늘 공부해볼 알고리즘은 BFS!!

 

알고리즘공부를 시작할 때 나를 가장 괴롭혔던,,,, ㅠㅠ

 

단순히 트리 형식으로 그림만 봤을때는 이해가 쉬운데

코드로 보려고 하다보니까

혼란스러웠던 기억이 난다.

 

BFS는 너비우선 탐색이다!

가장 이해하기 쉬운 트리형태의 그림으로 보면

 

bfs는 1->2->3->4->5->6->7 순서로 이동한다.

 

반면에 dfs는

 

1->2->4->5->3->6->7 순서로 이동한다.

 

dfs 와 bfs 각각 장단점이 있지만 

bfs는 최단거리를 찾을 때 주로 사용된다!

 

dfs는 모든 길을 다 가보고 길이를 비교하면서 최단 거리를 찾게 된다.

따라서 시간이 오래 걸리게 된다.

 

하지만 bfs는 너비우선탐색으로 한번에 탐색하므로

dfs에 비해서 시간이 적게 걸린다!

 

다음으로는 큐에 담기는 과정을 봐보자

 

첫 번째로 1번 노드를 큐에 담는다.

 

그 다음으로 1번과 연결된 노드인 2번과 3번 노드를 큐에 담고,

1번 노드는 pop을 해준다!

 

다음으로 2번과 연결된 3,4번 노드를 큐에 넣어주고

2번 노드를 pop해준다.

 

같은 방식으로 3번 노드와 연결된 6,7번 노드를 큐에 넣어주고,

3번 노드를 pop해준다.

 

마지막에 4,5,6,7번 노드는 연결된 노드가 없으므로

모두 pop해준다!

 

이러한 과정을 코드로 구현해보겠다.

 

( 손으로 작성했더니 너무 엉망ㅎ.....)

(학교다닐 때 알고리즘 과제와 시험이 손코딩이라서.. 정말 싫었지만

손코딩이 이해하는데는 짱인 것 같다.... 그래서 포기 못한다,,, 흑)

 

여튼! 

기본 구조는 이런 식이다.

먼저 시작점을 큐에 넣어주고,

while문을 돌리면서 큐에서 빼주고 빼준 지점과 연결된 모든 지점을 큐에 넣어주고..!

 

하지만 파이썬으로 저런식으로 코딩하면 시간초과가 발생할지도 모른다 ㅠ

(그게 바로 방금...)

 

왜냐하면 q.pop(0)에서 첫 번째꺼를 pop하는데 걸리는 시간복잡도가 O(n)이라고 한다!

따라서 deque를 써주는 것을 추천한다

deque는 시간복잡도가 O(1)이다!!

 

deque를 사용한 bfs 코드