1012. 유기농 배추

1. 해결방법

• 배추가 있는 위치에서 BFS 탐색한다. 1) 배추 위치 저장  2) 배추 위치 개수 v.size() 만큼 BFS
• BFS는 Queue에 한뭉텅이 원소들을 push()하며,원소의 주변을 탐색한다. 

2. Solution

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

#define endl "\n"
#define MAX 50
using namespace std;

int T, M, N, 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 BFS(int a, int b){
    queue<pair<int, int> > q;
    q.push(make_pair(a, b));
    visit[a][b] = true;

    // 한뭉텅이 탐색 : queue 하나가 한뭉텅이
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int d = 0; d < 4; d++)
        {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if(nx < 0 || nx >= M || ny < 0 || ny >= N) continue;

            if(!visit[nx][ny] && map[nx][ny] == 1)
            {
                q.push(make_pair(nx, ny));
                visit[nx][ny] = true;
            }
        }
    }

    // 한뭉텅이 탐색 후 Answer 증가
    Answer += 1;
}


int main(){
    cin >> T;
    for (int t = 0; t < T; t++)
    {
        // 입력받기
        Initialize();
        cin >> M >> N >> K;

        int X, Y;
        for (int k = 0; k < K; k++)
        {
            cin >> X >> Y;
            map[X][Y] = 1;
            v.push_back(make_pair(X, Y));
        }

        // 배추가 있는 위치에서 BFS 탐색
        for (int i = 0; i < v.size(); i++)
        {
            int x = v[i].first;
            int y = v[i].second;

            if (!visit[x][y])
            {
                BFS(x, y);
            }
        }
        cout << Answer << endl;
    }

    return 0;
}

 

3. 알아야 할 개념

• memset() : 배열 초기화

#include <cstring>

memset(배열명, 초기화value, sizeof(배열명));