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

문제 링크

 

풀이

전형적인 그래프 탐색 문제입니다. 문제에서 X좌표는 (행, 열) 중에 '열', Y좌표는 '행'에 해당합니다. 밭을 이차원 벡터로 표현하고 배추를 탐색한 곳은 확인하는 bool형 이차원 벡터도 필요합니다.

 

코드

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int main()
{
	int T, M, N, K;
	//     c  r  배추

	scanf("%d", &T);	

	int r_dir[] = {0, 1, 0, -1};
	int c_dir[] = {1, 0, -1, 0};

	while (T--)
	{
		scanf("%d", &M);
		scanf("%d", &N);
		scanf("%d", &K);
		vector<vector<int>> map(N, vector<int>(M, 0));
		vector<vector<bool>> checked(N, vector<bool>(M, false));
		queue<pair<int, int>> q;
		int count = 0;
		for (int i = 0; i < K; ++i)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			map[b][a] = 1;
		}

		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < M; ++j)
			{
				if (false == checked[i][j] && map[i][j])
				{
					++count;
					q.push({ i, j });
					checked[i][j] = true;
					while (!q.empty())
					{
						auto [row, col] = q.front();
						q.pop();

						for (int k = 0; k < 4; ++k)
						{
							int r = row + r_dir[k];
							int c = col + c_dir[k];
							if (r < 0 || r + 1 > N || c < 0 || c + 1 > M) continue;

							else if (false == checked[r][c] && map[r][c])
							{
								checked[r][c] = true;
								q.push({ r, c });
							}
						}
					}
				}
			}
		}
		printf("%d\n", count);
	}
}