[백준] 1012 - 유기농 배추, C++

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

1012번: 유기농 배추

 본 문제는 bfs와 dfs로 풀 수 있다. 비슷한 문제가 참 많다. 그래서 문제를 많이 풀어본 사람들은 쉽게 풀 수 있다. 그러나 난 x, y의 값 때문에 실수를 했다. 보통 row의 개수를 n, col의 개수를 m으로 많이 나온다. 문제를 제대로 읽지 않고 풀었다가 틀렸다. 결론은 문제를 잘 읽어야 한다.

#include <cstdio>
#include <cstring>
#include <queue>
 
using namespace std;
 
int d[51][51];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool chk[51][51];
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int m, n, k, x, y;
        scanf("%d %d %d", &m, &n, &k);
        memset(d, 0, sizeof(d));
        memset(chk, false, sizeof(chk));
        for (int i = 0; i < k; i++) {
            scanf("%d %d", &x, &y);
            d[x][y] = 1;
        }
        int cnt = 0;
        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!chk[i][j] && d[i][j] == 1) {
                    q.push(make_pair(i, j));
                    chk[i][j] = true;
                    cnt += 1;
                    while (!q.empty()) {
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();
                        for (int i = 0; i < 4; i++) {
                            int nx = x + dx[i];
                            int ny = y + dy[i];
                            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                                if (!chk[nx][ny] && d[nx][ny] == 1) {
                                    q.push(make_pair(nx, ny));
                                    chk[nx][ny] = true;
                                }
                            }
                        }
                    }
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}