[백준 1012번] 유기농 배추 (C, C++)

[백준 1012번 유기농 배추 URL]

https://www.acmicpc.net/problem/1012

[유사 문제]

2019/02/11 - [알고리즘 문제/백준(BOJ)] - [백준 2667번] 단지번호붙이기

이 문제는 [백준 2667번 단지번호 붙이기]와 거의 똑같은 문제라고 볼 수 있습니다.

#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
#define MAX 50
 
int n, m, k;
 
int dir[4][2] = {
    {1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
 
int map[MAX][MAX];
bool visited[MAX][MAX];
 
bool boundary(int row, int col) {
    return (row >= 0 && row <= n) && (col >= 0 && col < m);
}
 
void show() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout.width(5);
            cout << map[i][j] << " ";
        }
        cout << endl;
    }
}
 
void bfs(int row, int col) {
 
    queue<pair<int, int> > q;
    q.push(make_pair(row, col));
    visited[row][col] = true;
 
    while (!q.empty()) {
 
        pair<int, int> p = q.front();
        q.pop();
        int cx = p.first;
        int cy = p.second;
        
 
        for (int i = 0; i < 4; i++) {
 
            int nx = cx + dir[i][0];
            int ny = cy + dir[i][1];
 
            if (!visited[nx][ny] && map[nx][ny] == 1 && boundary(nx, ny)) {
                visited[nx][ny] = true;
                q.push(make_pair(nx, ny));
            }
 
        }
    }
}
 
void dfs(int row, int col) {
 
    
    visited[row][col] = true;
 
    for (int i = 0; i < 4; i++) {
 
        int nr = row + dir[i][0];
        int nc = col + dir[i][1];
 
        if (boundary(nr, nc) && !visited[nr][nc] && map[nr][nc] == 1)
            dfs(nr, nc);
        
    }
 
}
 
 
int main(void) {
 
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
 
        memset(visited, false, sizeof(visited));
        memset(map, 0, sizeof(map));
        cin >> m >> n >> k;
 
        for (int i = 0; i < k; i++) {
            int row, col;
            cin >> col >> row;
            map[row][col] = 1;
        }
 
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    //bfs(i, j);
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
 
    }
 
    return 0;
}