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

✅ DFS

DFS는 시작 정점에서 갈 수 있는 길을 끝까지 파고들어가며 탐색하는 알고리즘
더 이상 갈 곳이 없으면 되돌아오면서 다른 길을 탐색한다

• 한 방향으로 깊게 탐색
• 방문한 곳을 기록하여 무한루프 방지
• 재귀함수 or 스택으로 구현 가능

---

✅ 특징

 

사용 구조	스택 (보통 재귀로 구현)
탐색 순서	한 방향으로 깊게 파고들기
주로 쓰는 상황	모든 경로 탐색, 연결 요소 개수 구하기
장점	구현이 간단하고 직관적임
단점	깊이가 너무 깊으면 재귀 제한에 걸릴 수 있음

 

---

✅ DFS 기본 구조 (2D 맵 기반)

void dfs(vector<vector<char>>& grid, int x, int y, int N, char color) {
    // 방문 처리
    grid[y][x] = 0;

    // 상하좌우 방향
    int dx[] = {0, 0, -1, 1};
    int dy[] = {-1, 1, 0, 0};

    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 범위 확인 + 아직 같은 색인 곳만 탐색
        if (nx >= 0 && nx < N && ny >= 0 && ny < N && grid[ny][nx] == color) {
            dfs(grid, nx, ny, N, color); // 재귀 호출
        }
    }
}

---

✅ 단계별 설명

1. 함수 호출 시, 현재 위치 x, y, 색깔 color 받음

void dfs(..., int x, int y, ..., char color)

→ 현재 (x, y) 위치를 기준으로 같은 색을 가진 인접 칸들을 계속 탐색할 것임

---

2. 방문 처리

grid[y][x] = 0;

→ 현재 칸은 이미 방문했기 때문에 다시 방문하지 않도록 0으로 처리

---

3. 상하좌우 탐색

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

→ 순서대로 위, 아래, 왼쪽, 오른쪽으로 탐색
→ x + dx[i], y + dy[i]로 새로운 좌표 만들기

---

4. 범위 및 조건 확인 후 재귀 호출

if (nx >= 0 && nx < N && ny >= 0 && ny < N && grid[ny][nx] == color) {
    dfs(grid, nx, ny, N, color);
}

→ 새 좌표가 격자 범위 안에 있고
→ 아직 방문하지 않았고, 색이 같은 경우
→ → 재귀 호출로 계속 깊이 탐색

---

✅ 시각적으로 보면

시작점 (1, 1)에서 시작
→ (1,1)이 R이면, 그 주변의 R을 찾고
→ 또 그 주변의 R을 찾고...
→ 더 이상 없으면 백트래킹해서 다른 방향으로 이동
→ 한 색깔 영역을 전부 탐색하면 종료

---

 

✅ DFS vs BFS 비교 요약

구조	스택 / 재귀	큐 (queue)
탐색 순서	깊게 파고들기	가까운 곳부터 차례대로
구현 방식	재귀, 혹은 수동 stack 사용	queue 사용
장점	코드 간단, 구현 직관적	최단 거리 보장
단점	재귀 깊으면 스택 오버플로우	메모리 사용량 높을 수 있음

---

✅ Stack 을 활용한 DFS

재귀 호출이 깊으면 스택 오버플로우 위험 있음	특히 큰 입력(예: 1000x1000)일 때
반복문만으로 DFS 구현 가능	재귀를 피하고자 할 때 유용
명시적 스택 구조를 이해하는 데 도움 됨	DFS 작동 방식이 더 잘 보임

 

---

✅ 기본 구조: 재귀 DFS → 반복문 + stack

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void dfs_stack(vector<vector<char>>& grid, int x, int y, int N, char color) {
    int dx[] = {0, 0, -1, 1};   // 상하좌우
    int dy[] = {-1, 1, 0, 0};

    stack<pair<int, int>> st;
    st.push({x, y});
    grid[y][x] = 0;  // 방문 처리

    while (!st.empty()) {
    //DFS는 스택이 빌 때까지 계속함. 하나 꺼내고 → 그 이웃들을 다시 넣고 → 하나 꺼내고 ... 이런 식으로 반복.
        auto [cx, cy] = st.top();
        st.pop();

        for (int i = 0; i < 4; ++i) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
			
            // 유효성 검사 + 아직 안 간 곳이면 방문
            if (nx >= 0 && nx < N && ny >= 0 && ny < N && grid[ny][nx] == color) {
                grid[ny][nx] = 0;        // 방문 처리
                st.push({nx, ny});       // 다음 탐색할 좌표
            }
        }
    }
}

---

✅ 주요 흐름 비교

재귀 DFS	스택 DFS
dfs(x, y) 함수 안에서 재귀 호출	stack.push(x, y) 하고 반복문 사용
함수 콜 스택이 자동으로 관리됨	stack 컨테이너로 직접 스택을 관리함
깊게 들어가면 시스템 스택에 쌓임	직접 스택에 좌표를 넣고 빼며 탐색함

 

---

✅ 예시 사용 코드

int countRegion(vector<vector<char>>& grid, int N) {
    int cnt = 0;
    for (int i = 0; i < N; ++i){
        for (int j = 0; j < N; ++j){
            if (grid[i][j] != 0){
                dfs_stack(grid, j, i, N, grid[i][j]);
                cnt++;
            }
        }
    }
    return cnt;
}

 

✅ 요약 비교

stack	방문할 위치를 기억해두는 자료구조 (재귀 대신)
방문처리	방문한 위치는 0으로 바꾸어 중복 탐색 방지
4방향 확인	인접한 칸을 모두 살펴보고 조건 만족하면 push
while 반복	스택이 빌 때까지 반복하며 DFS 완성

왜 먼저 방문 처리 ?	이미 넣은 좌표를 또 중복해서 넣는 걸 막기 위해서!
재귀 DFS랑 순서가 완전히 똑같은가?	대부분 동일하나, 스택 DFS는 넣는 순서에 따라 순서가 다를 수 있음
grid[y][x] = 0?	문자열이 아니라 숫자로 미리 바꾸면 더 명확해짐 (1을 0으로 바꾸는 식)

---

✅ 팁: 재귀를 스택으로 바꾸는 요령

1. dfs(x, y) → stack.push({x, y})
2. return 없음 → while문 끝에서 자동종료
3. 방문 순서 보장 필요 없다면 그냥 stack 쓰면 됨

---

✅ 마무리

• 스택 DFS는 재귀 DFS를 안전하게 바꾼 방식이에요.
• 스택을 직접 다루며 재귀의 내부 구조를 더 명확히 이해할 수 있어요.
• 큰 맵 탐색 문제에 특히 안정적입니다.