백준 1012 유기농 배추 C++

백준 1012 유기농 배추.

백준 1012번 "유기농 배추" 문제의 자세한 내용은 글 하단의 문제 링크를 참고하세요.

1012번 문제에 주어지는 입력 및 예시

입력: 

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

출력:

5
1

코드

백준 1012번 "유기농 배추" 문제의 코드입니다.

#include <bits/stdc++.h>
using namespace std;
struct Node {int y, x;};
int DirectionY[4] = {-1, 0, 1, 0};  // 위 오 아 왼
int DirectionX[4] = {0, 1, 0, -1};
int a[51][51];
bool visited[51][51];
int main() {
    int T, n, m, k, x, y, num;
    cin >> T;
    while (T--) {
        memset(a, 0, sizeof(a));
        memset(visited, 0, sizeof(visited));
        num = 0;
        cin >> m >> n >> k;
        for (int i = 0; i < k; i++) {
            cin >> x >> y;
            a[y][x] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == 1 && visited[i][j] == 0) {
                    queue<Node> q;
                    q.push({i, j});
                    visited[i][j] = 1;
                    while (!q.empty()) {
                        Node node = q.front(); q.pop();
                        for (int ii = 0; ii < 4; ii++) {
                            int dx = node.x + DirectionX[ii];
                            int dy = node.y + DirectionY[ii];
                            if (dy < 0 || dx < 0 || dy >= n || dx >= m) continue;
                            if (a[dy][dx] == 0 || visited[dy][dx] == 1) continue;
                            visited[dy][dx] = 1;
                            q.push({dy, dx});
                        }
                    }num++;
                }
            }
        }
        cout << num << "\n";
    }return 0;
}

실행

위의 코드를 예제의 입력을 넣어 실행했을 때의 결과입니다.

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

1012번: 유기농 배추