[BFS] 백준 1012: 유기농 배추

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

 

배추흰지렁이는 그냥 문제를 더 풍부하고 재미있게 해 줄 요소일 뿐이고, 결국 '배추 클러스터 개수'를 묻는 문제이다.

 

void bfs(vector<vector<int>> &farm, vector<vector<bool>> &isVisited, int x, int y, int &answer)
{
    queue<pair<int,int>> queue;

    if(farm[x][y]==1&&!isVisited[x][y])
    {
        isVisited[x][y] = true;
        queue.push(pair<int,int>(x,y));
        answer++;
    }

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

        for(int i=0;i<4;i++)
        {
            int newX = currentCoord.first+dx[i];
            int newY = currentCoord.second+dy[i];

            if(newY<0||newX<0||newY>=M||newX>=N) continue;

            if(farm[newX][newY]==1 && !isVisited[newX][newY])
            {
                isVisited[newX][newY] = true;
                queue.push(pair<int,int>(newX, newY));  
            }
        }
    }
}

 

각 좌표에 대해, 만약 해당 좌표에 1. 배추가 심어져 있고 2. 아직 해당 좌표를 방문한 적이 없다면 배추 클러스터의 갯수를 +1 해 준다. 그리고 BFS를 수행하여 인접한 모든 배추를 방문 처리해 주면 해당 좌표와 연관된 배추 클러스터 하나를 체크하게 된다. 

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dx[] = {-1,0,1,0};
int dy[] = {0,-1,0,1};

int N, M;

void bfs(vector<vector<int>> &farm, vector<vector<bool>> &isVisited, int x, int y, int &answer)
{
    queue<pair<int,int>> queue;

    if(farm[x][y]==1&&!isVisited[x][y])
    {
        isVisited[x][y] = true;
        queue.push(pair<int,int>(x,y));
        answer++;
    }

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

        for(int i=0;i<4;i++)
        {
            int newX = currentCoord.first+dx[i];
            int newY = currentCoord.second+dy[i];

            if(newY<0||newX<0||newY>=M||newX>=N) continue;

            if(farm[newX][newY]==1 && !isVisited[newX][newY])
            {
                isVisited[newX][newY] = true;
                queue.push(pair<int,int>(newX, newY));  
            }
        }
    }
}

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

    int T;
    cin>>T;
    for(int i=0;i<T;i++)
    {
        int K;
        cin>>M>>N>>K;

        vector<vector<int>> farm(N, vector<int>(M));
        vector<vector<bool>> isVisited(N, vector<bool>(M, false));

        int x, y;
        for(int j=0;j<K;j++)
        {
            cin>>x>>y;
            farm[y][x] = 1;
        }

        int answer = 0;
        
        for(int s=0;s<N;s++)
        {
            for(int k=0;k<M;k++)
            {
                bfs(farm, isVisited, s,k, answer);
            }
        }

        cout<<answer<<"\n";
    }
}