[알고리즘 이론] 4. DFS, BFS

DFS (Depth-First Search)

• 루트 노드(다른 임의의 노드도 가능)에서 다음 분기(branch)로 넘어가기 전에, 해당 분기(branch)를 모두 탐색하는 방법.
• 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색한다.

특징

1. 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다. -> 재귀 or 스택
2. 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부르 반드시 검사해야 한다.
   • 이를 검사하지 않으면 무한루프에 빠질 수 있다.
   • EX) visit[node] = true;
3. 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더이상 갈 수 업게 되면 다시 가장 가까운 갈림길로(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
4. 모든 노드를 방문하고자 할 때, 이 방법을 선택한다.
5. BFS 보다 구현이 간단하다.
6. 검색 속도 자체는 BFS보다 느리다.

코드

// DFS, 재귀, 인접 행렬, i 정점부터 시작한다. -> 총 노드 수 n개
public static void dfs(int i) {
    visit[i] = true; 

    for (int j = 1; j < n+1; j++) {
        if(map[i][j] == 1 && visit[j] == false) { 
            dfs(j); 
        }
    }

}

BFS (Breadth-First Search)

• 루트 노드(다른 임의의 노드도 가능)에서 시작한 인접 노드를 먼저 탐색하는 방법.

특징

1. BFS는 재귀적으로 동작하지 않는다.
2. BFS 또한, 구현할 때 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.
3. BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐를 사용한다. -> 선입선출을 원칙으로 탐색한다.
4. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
5. 깊게 탐색하기 전에 넓게 탐색하는 것이다.
6. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다.
   • 전체 노드 중 두 노드 사이의 경로를 찾는 경우
     • DFS는 모든 노들르 살펴봐야 할 수도 있다.
     • BFS는 두 노드중 한 노드와 가까운 관게부터 탐색한다. -> 빠르다.

코드

// BFS, 큐 사용, 인접행렬, i 정점부터 시작한다.
public static void bfs(int i) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(i);
    visit[i] = true;

    while(!queue.isEmpty()) {
        int temp = queue.poll();

        for(int j = 1; j < n+1; j++) {
            if(map[temp][j] == 1 && visit[j] == false) {
                queue.offer(j);
                visit[j] = true;
            }
        }
    }
}

DFS와 BFS의 차이점

• DFS는 깊게, BFS는 넓게 탐색한다.

알고리즘 문제 추천

1. DFS와 BFS (실버 2)

• https://www.acmicpc.net/problem/1260

2. 미로 탐색 (실버 1)

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

3. 숨바꼭질 2 (골드 4)

• https://www.acmicpc.net/problem/12851

4. 숨바꼭질 3 (골드 5)

• https://www.acmicpc.net/problem/13549

5. 숨바꼭질 4 (골드 4)

• https://www.acmicpc.net/problem/13913

6. 이모티콘 (골드 4)

• https://www.acmicpc.net/problem/14226

7. 아기 상어 2 (실버 2)

• https://www.acmicpc.net/problem/17086

8. 달리기 (플래티넘 3)

• https://www.acmicpc.net/problem/16930

참고 자료

https://bbangson.tistory.com/42