유기농 배추 1012

문제

접근 방법

영역이 몇 개 있는지 확인하는 문제이다. Bool 이차원 배열로 영역을 체크해주면 된다. DFS, BFS 둘 다 사용할 수 있는 문제일 것이다.

코드

#include <iostream>
#include <cstring>
using namespace std;
bool map[51][51];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, M, N;
void dfs(int y, int x)
{
    map[y][x] = false;
    for (int i = 0; i < 4; ++i)
    {
        int nextX = x + dx[i];
        int nextY = y + dy[i];
        if (nextY < 0 || nextX < 0 || nextY >= N || nextX >= M)
            continue;
        if (map[nextY][nextX])
        {
            dfs(nextY, nextX);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    while (T--)
    {
        int K, cnt = 0;
        cin >> M >> N >> K;
        memset(map, false, sizeof(map));
        for (int i = 0; i < K; ++i)
        {
            int X, Y;
            cin >> X >> Y;
            map[Y][X] = true;
        }
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < M; ++j)
            {
                if (map[i][j])
                {
                    cnt++;
                    dfs(i, j);
                }
            }
        }
        cout << cnt << "\n";
    }
    return 0;
}

풀이

쉬운 유형의 탐색 문제이다. x, y 축으로 이동하며 영역을 체크해주면 된다. 같은 영역을 DFS, BFS를 활용하여 모두 false로 바꿔주면 다음 반복문에 진입할 때는 다른 영역이라는 점을 활용해주면 된다.