BFS, DFS (너비 우선 탐색, 깊이 우선 탐색)

 구현 관련 알고리즘만 풀다가 드디어 시작했다... 바로 레츠고~

 우선 BFS, DFS는 그래프 형태에서 탐색을 진행하는 방법이다. 노드(node)와 간선(edge)의 구성으로 이루어진 그래프 형태에서 사용한다. 이때 그래프는 2차원 행렬을 사용해서 연결 노드를 표시하거나(list[1][3] = 8  -> 1번 3번 노드는 거리가 8이다. 연결되어있지 않은 노드 사이에는 0, 본인 노드는 list[1][1]은 INF 쓰레기값을 넣는다.)  인접 리스트 방식으로 (graph[0].append((1,7)) -> 0번 노드는 1번 노드와 거리 7이다.) 표현한다. 2차원 행렬은 연결되어 있지 않은 노드들도 표현하며 인접 리스트는 연결이 되어 있는 정보만 갖고 있는다. 

 BFS(너비 우선 탐색)

 가까운 노드부터 탐색하는 알고리즘이다. 시작 노드를 기준으로 가까운 노드부터 탐색한다. queue를 사용한다. (파이썬을 사용할 때는 스택과 큐의 역할을 모두하는 deque가 속도가 빠르므로 deque를 사용한다.) 

 

1. 시작 노드를 큐에 넣는다.

2. 큐에서 노드를 꺼낸 후 해당 큐와 연결되어 있는 노드를 큐에 넣는다.

3. 큐가 empty일 경우까지 2번을 반복한다.

 DFS(깊이 우선 탐색)

 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택을 사용하는데 컴퓨터 특성상 재귀 함수가 스택으로 작동하므로 재귀 함수를 활용한다. 

 

1. 시작 노드를 기점으로 for를 사용하거나, 이동 방향을 설정하여 다음 노드를 기점으로 재귀적으로 DFS를 실행한다.

 

 DFS 설명이 조금 애매한데 해보면 안다! for를 이용한 재귀함수이기에 for의 i가 0일때 DFS를 실행하면 그 노드를 타고 타고 모든 노드를 수행한 후 다시 돌아와 i가 1일 경우의 DFS를 재귀로 다시 돌리기 때문에 DFS 알고리즘이 실행된다!

 비교 & 활용

검색 속도는 BFS가 더 빠르다고 나와있는 설명이 있으나 여러 자료를 찾아보니 문제의 상황에 따라 다르다. 시작 노드와 탐색 대상의 노드가 가까이 있을 경우 BFS가 더 빠르다. 경로의 특징을 저장해야 하는 경우에는 DFS가 더 효율적이다. 그리고 보통 삽입 삭제등의 시간 복잡도가 큐가 더 효율적이므로 BFS를 사용했을 때(큐를 사용하는 알고리즘 이 BFS)가 좋은 경우가 많다고 한다. 

BFS - 최단 경로, 동시 탐색        DFS - 모든 그래프 순회, 백 트래킹(진행하다가 조건에 맞지 않을 때 뒤로 돌아가는 경우)

 위의 예시가 정답은 아니다. 알아서 상황에 맞는 알고리즘을 선택해야한다~

 

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색