[ 백준 1012 ] 유기농배추 (C++)

백준 유기농배추(1012) 문제입니다.

( www.acmicpc.net/problem/1012 )

[ 문제설명 ]

- 맵의 크기와 맵에서 배추가 심어져 있는 갯수와, 각각의 배추가 심어져 있는 위치를 입력받습니다.

- 서로 인접한 배추가 있는 곳에서는 배추흰지렁이가 옮겨 다닐 수 있고, 배추가 없는 곳으로는 갈 수 없습니다.

- 결과적으로 총 몇마리의 지렁이가 필요한지 구하는 문제입니다.

[ 풀이방법 ]

1) 배추가 심어져 있는 좌표점을 입력받을 때, 맵에 해당 좌표를 '1' 로 설정합니다.

2) 필요없는 반복문을 제거해주기 위해서 처음부터 배추가 있는 위치에서만 BFS탐색을 할 수 있도록 배추의 위치를 벡터에 

   넣어줍니다.

3) BFS탐색 하면서, BFS탐색을 한번 할 때 마다 지렁이의 갯수(Answer)를 ++ 시켜주면 됩니다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M, K, Answer;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
vector<pair<int, int>> V;
 
void Initialize()
{
    Answer = 0;
    memset(MAP, 0, sizeof(MAP));
    memset(Visit, false, sizeof(Visit));
    V.clear();
}
 
void Input()
{
    cin >> M >> N >> K;
    for (int i = 0; i < K; i++)
    {
        int x, y;
        cin >> x >> y;
        MAP[y][x] = 1;
        V.push_back(make_pair(y, x));
    }
 
    /*for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cout << MAP[i][j] << " ";
        }
        cout << endl;
    }*/
}
 
void BFS(int a, int b)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (Visit[nx][ny] == false && MAP[nx][ny] == 1)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
    Answer++;
 
}
 
void Solution()
{
    for (int i = 0; i < V.size(); i++)
    {
        int x = V[i].first;
        int y = V[i].second;
 
        if (Visit[x][y] == false)
        {
            //cout << "(x,y) = (" << x << "," << y << ")" << endl;
            BFS(x, y);
        }
    }
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}