1012번 - 유기농 배추(c++)

🗒 1012번 문제

📌 DFS를 사용해서 구현한 문제 ❗️

1️⃣ 위, 아래, 왼쪽, 오른쪽에 지렁이가 있으면 다른 배추로 이동 가능

2️⃣ 인접해 있는 배추로 지렁이의 수를 알아보자

3️⃣ dx, dy 배열을 사용해서 4방향 탐색을 하자

4️⃣ dfs로 구현했기에 해당 노드에서 인접 배추가 없을 때까지 배추 찾고 다른 배추로 넘어감
-> 재귀 함수로 dfs를 호출

5️⃣ 한 번 노드를 탐색하러 들어가면 인접한 걸 찾을 때까지 dfs함수밖으로 나오지 않기 때문에 
   탐색 시작 노드에서 count를 +1하기

➰ 코드로 나타낸 1012번 ➰

#include <iostream>
#include <algorithm>

using namespace std;

int row, col, pos;
int map[50][50] = { 0 };
bool entered[50][50];

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

// testCase를 반복하기에 그 때마다 map를 초기화
void init() {
    for (int i = 0; i < 50; i++) {
        for (int j = 0; j < 50; j++) {
            map[i][j] = 0;
        }
    }
}

void dfs(int px, int py) {
    if (map[px][py] == 1) {
    // 배추가 있으면 해당 배추를 이미 접근했기에 0으로 만들고 사방에서 인접 배추 찾기
        map[px][py] = 0;
        for (int i = 0; i < 4; i++) {
            int qx = dx[i] + px;
            int qy = dy[i] + py;
            if (qx >= 0 && qy >= 0 && qx < row && qy < col)
                dfs(qx, qy);
                // 찾으면 dfs로 그 배추의 인접 배추 찾기
        }
    }
}

int main() {
    int testCase;
    cin >> testCase;
    
    // testCase를 다 끝낼 때까지
    while (testCase--) {
        int count = 0;
        int px, py;
        init();
        
        cin >> row >> col >> pos;
        for (int i = 0; i < pos; i++) {
            cin >> px >> py;
            map[px][py] = 1;
            // 배추가 있는 위치 받기
        }
        
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (map[i][j] == 1) {
                // 배추가 있는 시작 노드를 찾으면 count+1하고 dfs로 인접배추 찾기
                    count++;
                    dfs(i, j);
                }
            }
        }
        
        cout << count << endl;
    }
    
    return 0;
}