[DFS 알고리즘] 문제풀이 전략

---

DFS는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다

 

가장 깊은 부분 탐색 이후에 다시 거슬러 올라오는 과정이 필요하므로 과정을 기록할 수 있는 Stack을 주로 사용한다

 

동시에 깊이를 확인하여 다시 올라갈지 결정해야 하므로 재귀 함수를 사용한다

 

대표 예제를 통해 이를 연습해보자

---

문제 : N*M 크기의 얼음 틀이 존재한다. 얼음 틀 모양이 주어졌을 때 생성되는 아이스크림의 수를 구하라

 

입력 조건

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다 (1<=N,M<=1000)
• 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다
• 구멍이 뚫려 있는 부분은 0, 그렇지 않은 부분은 1이다

출력 조건

• 한 번에 만들 수 있는 아이스크림의 개수를 출력한다

입력 예시 1

4 5
0 0 1 1 0
0 0 0 1 1
1 1 1 1 1 
0 0 0 0 0

출력 예시 1

3

---

BFS 방식으로 문제를 풀 수 있었지만 탐색하는 거리는 필요하지 않았기 때문에 DFS 방식으로 풀어 보았다

 

탐색 노드의 상하좌우를 탐색하면서 방문하지 않은 노드들을 다시 재귀적으로 탐색했다

---

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int n, m;
int ans;
int board[1001][1001];
int check[1001][1001];
void DFS(pair<int, int> p);
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            cin >> board[i][j];
            if (board[i][j] == 1) check[i][j] = -1;
        }
    }
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            if (check[i][j] == 0) {
                DFS({ i,j });
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}

void DFS(pair<int,int> p) {
    for (int dir = 0;dir < 4;dir++) {
        int mx = p.X + dx[dir];
        int my = p.Y + dy[dir];
        if (mx < 0 || my < 0 || mx >= n || my >= m) continue;
        if (check[mx][my] != 0) continue;
        check[mx][my] = 1;
        DFS({mx,my});
    }
}

---