[BOJ 1012] 유기농 배추 C++

유기농 배추

난이도: Silver 2
번호: 1012
사용 함수, 자료 구조: memset
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색
언어: C++

1012번: 유기농 배추

C++

BFS

#include <iostream>
#include <queue>
using namespace std;

const int dX[] = {1, -1, 0, 0};
const int dY[] = {0, 0, -1, 1};
int N, M, K, cnt;
bool node[51][51];
bool visited[51][51];

void reset()
{
    cnt = 0;
    for (int i = 0; i < 51; i++)
        for (int j = 0; j < 51; j++)
        {
            node[i][j] = false;
            visited[i][j] = false;
        }
}

void BFS(int i, int j)
{
    queue<pair<int, int>> Q;
    Q.push({i, j});
    visited[i][j] = true;

    while (!Q.empty())
    {
        pair<int, int> p = Q.front();
        Q.pop();

        for (int k = 0; k < 4; k++)
        {
            int x = p.first + dX[k];
            int y = p.second + dY[k];

            if (x < 0 || y < 0 || x >= N || y >= M)
                continue;

            if (!node[x][y] || visited[x][y])
                continue;

            Q.push({x, y});
            visited[x][y] = true;
        }
    }
    cnt++;
}

int main(void)
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);

    int T;
    cin >> T;

    while (T--)
    {
        reset();
        cin >> M >> N >> K;
        for (int i = 0; i < K; i++)
        {
            int x, y;
            cin >> x >> y;
            node[y][x] = true;
        }

        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                if (node[i][j] && !visited[i][j])
                    BFS(i, j);
        cout << cnt << '\n';
    }
}

C++ 2

DFS

#include <iostream>
#include <cstring>
using namespace std;

const int dX[] = {1, -1, 0, 0};
const int dY[] = {0, 0, -1, 1};
int N, M, K, cnt;
bool node[52][52];

void reset()
{
    cnt = 0;
    memset(node, 0, sizeof(node));
}

void DFS(int i, int j)
{
    node[i][j] = false;

    for (int k = 0; k < 4; k++)
    {
        int x = j + dX[k];
        int y = i + dY[k];
        if (node[y][x])
            DFS(y, x);
    }
}

int main(void)
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);

    int T;
    cin >> T;

    while (T--)
    {
        reset();
        cin >> M >> N >> K;
        for (int i = 0; i < K; i++)
        {
            int x, y;
            cin >> x >> y;
            // 0 ~ 52 중에서 1 ~ 50까지 쓴다 (out of bound 방지)
            node[y + 1][x + 1] = true;
        }

        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if (node[i][j])
                {
                    DFS(i, j);
                    cnt++;
                }
        cout << cnt << '\n';
    }
}