[C/C++] 백준 1012번 - 유기농 배추 (BFS)

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int map[51][51];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int M, N, K; // 가로, 세로, 배추 수
int T, u, v;
int earthworm;
queue<pair<int,int>> q;

void BFS(int x, int y)
{
	map[x][y] = 0;

	q.push(pair<int, int>(x, y));

	while (!q.empty())
	{
		int now_x = q.front().first;
		int now_y = q.front().second;
		
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int next_x = now_x + dx[i];
			int next_y = now_y + dy[i];
			if (next_x >= 0 && next_y >= 0 && next_x < N && next_y < M)
			{
				if (map[next_x][next_y] == 1)
				{
					map[next_x][next_y] = 0;
					q.push(pair<int, int>(next_x, next_y));
				}
			}
		}
	}
	earthworm++; 
}

int main() 
{
	ios::sync_with_stdio(0); 
	cin.tie(0); 

	cin >> T;

	while (T--)
	{
		// 맵 초기화
		for (int i = 0; i < 50; i++)
			for (int j = 0; j < 50; j++)
				map[i][j] = 0;

		earthworm = 0;

		cin >> M >> N >> K;

		for (int i = 0; i < K; i++)
		{
			cin >> u >> v;
			map[v][u] = 1;
		}

		for (int i = 0; i < 50; i++)
			for (int j = 0; j < 50; j++)
			{
				if (map[i][j] == 1) BFS(i, j);
			}

		cout << earthworm << '\n';

	}
}

 

 

 

www.acmicpc.net/problem/1012

1012번: 유기농 배추