[실전 알고리즘] 0x0A강 | 깊이 우선 탐색 (DFS) - 스택으로 DFS 구현하기 / DFS와 BFS의 차이?

 

🔎 DFS란?

 

BFS와 DFS를 쉽게 설명하자면,
가까운 이웃부터 좀좀따리 파면서 탐색. 한 단계씩 나아가며 가까운 정점들을 다 방문함 - 큐로 구현
드라마 정주행하듯 끝까지 깊이 탐색. 더이상 못 파면 이전으로 돌아가 다른 경로 탐색. - 스택과 재귀로 구현 

BFS: 가까운 것부터 차례대로 탐색 → 큐 사용 → 최단 경로 탐색에 유리
DFS: 깊게 탐색 후 되돌아감 → 스택 또는 재귀 사용 → 경로를 깊이 있게 탐색

 

지난 글에서 BFS를 다루며 언급했던 내용이다.

 

 DFS는 BFS와 크게 다를 것 없지만, 스택을 사용해 구현한다. BFS는 FIFO인 큐를 사용해서, 인접한 노드들을 우선적으로 처리하며 점차 퍼져나갔다면, DFS는 LIFO인 스택을 사용하기에 가장 최근에 들어갔던 마지막 노드가 우선 처리되므로, 가장 최근 것들을 깊고 깊게 파고 파는 마치 드라마 정주행같은.. 깊이 우선 탐색이 진행된다. 
 
이번 글에서는 바킹독 선생님의 강의를 기반으로, 스택을 활용해 DFS를 구현해보고, DFS와 BFS의 차이에 대해를 정리해 볼 것이다.

 

 

 

---

 

📝 스택을 활용해 DFS 구현하기

 

백준 2178번 미로탐색

- 2차원 좌표에서, 직사각형으로 가려지지 않은 부분의 개수와 각각의 넓이

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstring> // memset 사용

using namespace std;

int m, n, k, cnt = 0;
int board[101][101]; // 전역 배열은 자동으로 0으로 초기화됨
int dx[4] = {1, 0, -1, 0}; // 동, 남, 서, 북
int dy[4] = {0, 1, 0, -1};
vector<int> width;
stack<pair<int, int>> s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> m >> n >> k;
    
    memset(board, 0, sizeof(board)); // 모든 칸을 0으로 초기화

    // 직사각형 입력 받기
    while (k--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        for (int i = y1; i < y2; i++) { // 세로(y) 좌표 기준
            for (int j = x1; j < x2; j++) { // 가로(x) 좌표 기준
                board[i][j] = 1; // 직사각형을 1로 표시
            }
        }
    }

    // DFS를 이용한 영역 탐색
    for (int i = 0; i < m; i++) { // 세로(행)
        for (int j = 0; j < n; j++) { // 가로(열)
            if (board[i][j] != 0) continue; // 이미 방문했거나 직사각형이면 패스

            s.push({i, j});
            board[i][j] = 1; // 방문 표시
            cnt++; // 영역 개수 증가
            int w = 0; // 새로운 영역의 면적을 0으로 초기화

            while (!s.empty()) {
                pair<int, int> cur = s.top();
                s.pop();
                w++; // 면적 증가

                for (int d = 0; d < 4; d++) { // 4방향 탐색
                    int x = cur.first + dx[d];
                    int y = cur.second + dy[d];

                    if (x < 0 || x >= m || y < 0 || y >= n) continue; // 범위 체크
                    if (board[x][y] != 0) continue; // 이미 방문했거나 직사각형이면 패스

                    board[x][y] = 1; // 방문 표시
                    s.push({x, y});
                }
            }
            width.push_back(w); // 영역 크기 저장
        }
    }

    // 면적 오름차순 정렬
    sort(width.begin(), width.end());

    // 출력
    cout << cnt << '\n';
    for (int i = 0; i < width.size(); i++) {
        cout << width[i] << " ";
    }

    return 0;
}

  
 

---

 

📝 DFS vs BFS

 

BFS는 한 칸 씩 인접칸으로 이동해가는 반면, DFS는 가능한 깊이있게 우선 탐색을 하기 때문에, 거리 측정이 불가능하다. BFS는 큐를 써서 이전에 탐색한 칸과 가장 가까운 칸이 먼저 처리되지만, DFS는 일단 깊이 우선으로 냅다 파고보기 때문이다. (아래 그림 참고)

(출처) 바킹독 실전 알고리즘 DFS 강의 자료

 

 

앞으로 다차원 배열의 순회를 처리할 때는 무조건 BFS를 사용하라. 

영역 칠하기는 뭐 DFS를 써도 상관없지만, BFS는 거리측정이 가능하니깐 대부분의 문제에서 유용하게 쓰인다. 지금까지 배운 내용만으로는 굳이 BFS 말고 DFS로 풀어야하는 문제는 없다.

 

DFS는 이후 그래프와 트리 배울 때 필요하게 된대 ㅇㅇ

 

---

 

 

요약하자면 BFS와 DFS는 다차원 배열의 순회를 처리하는 알고리즘인데, BFS는 큐 / DFS는 스택을 사용한다.

 

• BFS (너비 우선 탐색)
  • 큐(Queue)를 사용하여 탐색하며, 가까운 노드(또는 인접한 셀)부터 탐색합니다.
  • 최단 경로 문제에 자주 활용됩니다.
• DFS (깊이 우선 탐색)
  • 스택(Stack) 또는 재귀 호출을 이용하여 탐색합니다.
  • 한 경로를 끝까지 깊게 탐색한 후, 다른 경로를 탐색합니다.

 

---

 

이번 DFS 파트는 강의 자체가 짧아서 금방 정리했지요 ~0~ 이제 재귀와 싸우러 가보자  . . . ㅎㅎ 아쟈아쟈.

 
(출처) [실전 알고리즘] 0x0A강 - DFS

[실전 알고리즘] 0x0A강 - DFS