DFS와 BFS 소개

DFS(깊이 우선 탐색, Depth-First Search)

한 경로를 끝까지 탐색한 후, 다시 돌아와서 다른 경로를 탐색하는 방식이다. 스택(재귀)을 사용해 구현한다.

코드

vector<int> g[1001]; // 벡터 배열
bool visited[1001]; // 방문한 노드 체크

void dfs(int s) { // 1. 시작 노드 방문
    visited[s] = true; // 2. 방문한 노드를 체크
    cout << s << " ";
    for (int idx : g[s]) {
        // 3. 인접한 노드를 재귀적으로 방문
        // 4. 더 이상 갈 곳이 없으면 이전 노드로
        if (!visited[idx])
            dfs(idx);
    }
}

동작 방식

1. 시작 노드부터 방문하면서 출력
2. 방문한 노드는 visited 배열에 체크
3. 인접한 노드를 재귀적으로 방문
4. 더 이상 갈 곳이 없으면 이전 노드로 되돌아감

사용 사례

미로 탐색, 사이클 탐지, 백트래킹 등

BFS(너비 우선 탐색, Breadth-First Search)

시작 노드에서 가까운 노드부터 탐색하는 방식이다. 큐를 사용해 구현한다.

코드

vector<int> g[1001]; // 벡터 배열
bool visited[1001]; // 방문한 노드 체크

void bfs(int s) {
    queue<int> q;
    q.push(s);        // 1. 시작 노드를 큐에 추가
    visited[s] = true; // 시작 노드 방문 처리

    while (!q.empty()) { // 4. 큐가 빌 때까지 반복
        int temp = q.front();
        q.pop();       // 2. 큐에서 노드를 꺼냄
        cout << temp << " ";

        for (int i : g[temp]) {
            if (!visited[i]) {
                q.push(i); // 3. 인접한 노드를 큐에 넣고 방문 
                visited[i] = true;
            }
        }
    }
}

동작 방식

1. 시작 노드를 큐에 넣고 방문 체크
2. 큐에서 노드를 꺼내면서 출력
3. 인접한 노드를 큐에 넣고 방문 체크
4. 큐가 빌 때까지 반복

DFS와 BFS의 차이점

알고리즘	자료구조	사용 사례
DFS	스택(재귀)	미로 탐색, 그래프 탐색
BFS	큐	최단 거리 문제, 네트워크 탐색