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

문제 링크: https://www.acmicpc.net/problem/1012

 

Labeling을 적당히 해주면 됩니다

입력된 점마다 BFS 또는 DFS로 탐색을 해서 연결된 부분을 전부 탐색한 뒤 bool visited[][]등에 저장해놓습니다. 이 때 counter를 1씩 증가시켜 주고요, 마지막에는 counter만 출력하면 완성입니다

저는 BFS로 풀었고요 label 배열을 만들어서 0이면 방문하지 않음, 1 이상이면 방문한 곳의 label 이렇게 사용을 했습니다.

// 1012
#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;


const int DIR[][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

int bachu[50][50];
int label[50][50];	//0: not visited


bool in_range(int y, int x, int height, int width) {
	return y >= 0 && y < height&& x >= 0 && x < width;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int t;
	cin >> t;
	while (t--) {
		memset(bachu, 0, sizeof(bachu));
		memset(label , 0, sizeof(label));

		int m, n;	//가로, 세로
		cin >> m >> n;

		int k;
		cin >> k;
		vector<pair<int, int>> pt(k);
		for (auto& p : pt) {
			cin >> p.second >> p.first;
			bachu[p.first][p.second] = 1;
		}

		
		int counter = 0;
		for (const auto& p : pt) {
			if (label[p.first][p.second]) continue;
			
			++counter;
			
			queue<pair<int, int>> q;
			q.emplace(p.first, p.second);
			label[p.first][p.second] = counter;

			while (!q.empty()) {
				auto current = q.front();
				q.pop();

				for (auto& d : DIR) {
					auto next_y = current.first + d[0];
					auto next_x = current.second + d[1];

					if (in_range(next_y, next_x, n, m) && bachu[next_y][next_x] && !label[next_y][next_x]) {
						label[next_y][next_x] = counter;
						q.emplace(next_y, next_x);
					}
				}
			}
		}

		cout << counter << '\n';
	}

	return 0;
}