들어가기에 앞서...

DFS와 BFS는 여러 코딩테스트(특히 삼성)의 단골 주제 입니다.
개발자 취업 준비생으로 필수로 알아야할 최우선순위로 학습해야 할 알고리즘입니다.
그 만큼 확실히 준비하여야하며, 어떤 변형 문제를 마주하더라도 풀 수 있는 실력을 갖추어야합니다.

그렇다면 기업들이 왜 탐색 알고리즘에 집중하는지 알아볼 필요가 있습니다.

1. 컴퓨팅 파워 - 탐색 알고리즘은 모두 순회하는 경우이기 때문에 연산량이 많다.
2. 디버깅하면서 문제 파악하기 어려움 - 연산량이 많으므로 사람이 각 케이스 별로 문제를 파악하기 쉽지 않다.
3. 프로그램 설계 실력 - 예외적인 상황을 고민하여 코드를 꼼꼼하게 구현해야한다. 처음 코드를 짜고 나서부터 완성할 때까지 코드 수정을 최소화해야 한다.

특징

DFS와 BFS 모두 Graph를 탐색하는 방법 입니다.

DFS와 BFS의 특징의 차이, 용법을 정확히 알고 적용해야한다. 단순히 깊이 vs 너비, 스택or재귀 vs 큐만으로 이해해서는 안된다.

DFS의 특징

DFS는 미로 탐색과 같습니다. 미로에서 끝이 나올때까지 깊이 들어가는 것처럼 DFS 또한 더 깊이 들어갈 수 없을때까지 탐색합니다.

• 설정한(먼저 보이는) 지점부터 방문한다.
• 한 번 방문한 지점은 다시 확인하지 않도록 마킹한다.
• 모든 노드를 방문하고 방문 여부를 체크 합니다. (체크하지 않을 시 무한루프)
• 간선이 끊어진 경우도 모든 노드를 탐색한다.

DFS의 장점 👍

• 설정한 경로의 노드를 기억하기 때문에 적은 메모리를 사용합니다.
• 찾으려는 노드가 깊은 단계에 있는 경우, 테스트케이스의 크기가 큰 경우, BFS보다 빠릅니다.
• 모든 경로를 탐색하고 그 결과를 확인해야 할 경우 유용합니다
• 문자열 등을 탐색할 때 "사전 순서로 앞에 오는 것"처럼 앞부터 검색해서 찾는 것이 빠를 경우 유용합니다.

DFS의 단점 👎

• 해이 없는 경로 탐색을 할 경우 끝까지 탐색합니다.
  • 효율성을 높이기 위해서 미리 지정한 임의 깊이까지 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용해야 합니다.
• DFS를 통하여 얻어진 해가 최단 경로라는 보장이 없습니다. DFS는 해에 도착하면 탐색을 종료합니다.

DFS의 구현

DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)

init() 
    For each u ∈ G
        u.visited = false
     For each u ∈ G
       DFS(G, u)

DFS를 이용한 알고리즘

• Flood Fill: 격자로 나타나는 묵시적 그래프에서 사용되는 알고리즘(웅덩이 채우기)
• Connected Components: 서로 연결되어 있는 여러 개의 부분 그래프
• Topological Sort(위상정렬): 어떤 일을 하는 순서를 찾는 알고리즘
• Strong Connected Components: 각 집합의 정점끼리 서로에게 도달할 수 있는 그래프
• Euler Circuit
• Articulation point & Bridge

DFS 문제 유형

방향 없는 연결 요소의 개수
단지번호 붙이기
섬의 개수
위상정렬-게임 개발
위상정렬-작업 최소 시간 구하기
강한 결합 요소-순열 사이클
강한 결합 요소-구현

BFS의 특징

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

• 시작점과 가까운 접점부터 방문합니다.
• 도달 가능한 정점들은 모두 방문합니다.
• level-by-level로 순회하는 특징을 가집니다.
• 재귀적으로 동작하지 않습니다.

BFS의 장점 👍

• 답이 되는 경로가 여러 개인 경우에도 최단경로를 보장합니다.
  • 지정된 노드에서 동일한 거리로 탐색하며 가장 가까운 목적지 노드에 먼저 도착함으로
• 탐색 범위 자체는 넓지만 어느 정도 근처에 구하고 싶은 해가 존재하는 것을 알고 있을 경우 용이합니다.
• 탐색 범위가 굉장히 넓으며 깊이 우선 탐색을 사용할 때 스택이 대략으로 사용되는 경우 대체가 용이합니다.

BFS의 단점 👎

• 경로가 매우 길어질 경우 탐색 가지가 급격히 증가함에 따라 많은 memory가 필요하게된다.
• 무한 그래프의 경우 결코 해를 찾지도 못하고, 끝내지도 못한다.

BFS의 구현

create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
    remove the head u of Q 
    mark and enqueue all (unvisited) neighbours of u

BFS를 이용한 알고리즘

• 최단 경로 알고리즘
• Bipartite Graph(이분 그래프): 한 집단의 점점과 연결된 정점이 다른 집단의 정점과 연결되어 있는 형태
• Khan's algoritm - Topological Sort(위상정렬): 어떤 일을 하는 순서를 찾는 알고리즘(DFS/BFS)

BFS가 사용되는 사례

Web crwaling
Network Broadcasting
Garbage Collection
Solving Puzzle & Games

BFS 문제 유형

• 토마토(2차원배열)
• 토마토(3차원배열)
• 이분 그래프-구현
• Khan's algoritm-구현

비교 정리

참고

DFS BFS란? 백준 문제추천
HI-ARC 정기모임 #6 dfs
HI-ARC 정기모임 #7 BFS
BFS & DFS 구분하자!
[알고리즘] 위상 정렬(Topological Sort)이란