1012번: 유기농 배추

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

구현 아이디어 5분 구현 15분

풀이

BFS를 활용해 풀면 된다. 테스트 케이스만 많아졌을 뿐 섬 개수 구하는 문제와 똑같다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;
int Dr[4] = {-1, 0, 1, 0};
int Dc[4] = {0, 1, 0, -1};

int main()
{
    int T{};
    scanf("%d", &T);

    for (int t = 0; t < T; ++t)
    {
        int M, N, K;
        scanf("%d %d %d", &M, &N, &K);

        vector<vector<int>> Maps(N, vector<int>(M, 0));

        for (int i = 0; i < K; ++i)
        {
            int X, Y;
            scanf("%d %d", &X, &Y);
            Maps[Y][X] = 1;
        }

        int Cnt{ 0 };

        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < M; ++j)
            {
                if (Maps[i][j] == 1)
                {
                    ++Cnt;
                    queue<pair<int, int>> Q;
                    Q.push(make_pair(i, j));
                    Maps[i][j] = 0;

                    while (!Q.empty())
                    {
                        int CurR = Q.front().first;
                        int CurC = Q.front().second;

                        Q.pop();
                        
                        for (int k = 0; k < 4; ++k)
                        {
                            int CheckR = CurR + Dr[k];
                            int CheckC = CurC + Dc[k];
                            if (CheckR < 0 || CheckC < 0 || CheckR >= N || CheckC >= M || 
                                Maps[CheckR][CheckC] == 0)
                                continue;
                            
                            Maps[CheckR][CheckC] = 0;
                            Q.push(make_pair(CheckR, CheckC));
                        }
                    }
                }
            }
        }

        printf("%d\n", Cnt);
    }

    return 0;
}

---

유사 문제

https://school.programmers.co.kr/learn/courses/30/lessons/154540