[BOJ_C++] 1012번 : 유기농 배추

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
#include <string>

using namespace std;

int n, m, k;
int arr[51][51];
bool visited[51][51];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };

void dfs(int x, int y) {
    int mx, ny;
    for (int i = 0; i < 4; i++) {
        mx = x + dx[i], ny = y + dy[i];

        if (ny < 0 || ny >= n || mx < 0 || mx >= m) continue;

        if (arr[mx][ny] && !visited[mx][ny]) {
            visited[mx][ny] = true;
            dfs(mx, ny);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T, cnt; cin >> T;
    int x, y;

    for (int tc = 0; tc < T; tc++) {
        memset(arr, 0, sizeof(arr));
        memset(visited, false, sizeof(visited));
        cin >> m >> n >> k;
        cnt = 0;
        for (int i = 0; i < k; i++) {
            cin >> x >> y;
            arr[x][y] = 1;
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] && !visited[i][j]) {
                    ++cnt;
                    visited[i][j];
                    dfs(i, j);
                }
            }
        }

        cout << cnt << "\n";
    }

    return 0;
}

• 배추의 좌표 x, y를 입력받은 후 배추가 있다는 의미로 arr[x][y]에 1을 넣어둔다.
• 밭의 넓이만큼 for문을 반복하며 배추가 존재하고 방문하지 않았다면 배추지렁이의 수(cnt)를 1 증가시키고 방문 표시를 한 뒤 근처에 있는 배추를 탐색한다.
• 근처 배추를 탐색하는 방법으로는 dfs를 사용하는데 이때 더 간편하게 하기 위해 지렁이가 움직일 수 있는 상하좌우 후 인덱스 변화 값을 미리 dx, dy 배열에 넣어둔다.
• 배추의 상하좌우로 mx, ny 값을 변경한 후 밭의 범위를 벗어난다면 다음 mx, ny를 구하고 아니라면 배추가 존재하는지 또 방문한 적 없는 배추인지 확인한다.
• 배추가 존재하며 방문한 적 없다면 방문 표시를 한 뒤 그 배추에 대하여 또 상하좌우를 탐색하게 된다.
• 주의할 점은 한 번 실행되는 것이 아니라 테스트 케이스가 주어지므로 각 테스트 케이스마다 arr과 visited를 초기화 해주어야 한다는 점이다.

결과