[BAEKJOON] 1012번 : 유기농 배추

문 제

 

소 스  코 드

#include <iostream>
#include <stack>

void CabbageField();

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int T, N, M;
	std::cin >> T;

	for (int i = 0; i < T; ++i) {
		CabbageField();
	}
	return 0;
}

void CabbageField() {
	int M, N, K;
	std::cin >> M >> N >> K;

	bool **field{ new bool*[N] };
	for (int i = 0; i < N; ++i) {
		field[i] = new bool[M];
		std::fill_n(field[i], M, false);
	}

	int X, Y;
	for (int i = 0; i < K; ++i) {
		std::cin >> X >> Y;
		field[Y][X] = true;
	}

	std::stack<std::pair<int, int>> logs;
	int num{ 0 };

	

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (!field[i][j]) continue;

			logs.push(std::make_pair(i, j));
			field[i][j] = false;
			++num;

			while (!logs.empty()) {
				int x = logs.top().first;
				int y = logs.top().second;
				logs.pop();

				// [x][y] [N][M]
				if ((x > 0) && (field[x - 1][y])) {
					field[x - 1][y] = false;
					logs.push(std::make_pair(x - 1, y));
				}

				if ((x < N - 1) && (field[x + 1][y])) {
					field[x + 1][y] = false;
					logs.push(std::make_pair(x + 1, y));
				}

				if ((y > 0) && (field[x][y - 1])) {
					field[x][y - 1] = false;
					logs.push(std::make_pair(x, y - 1));
				}

				if ((y < M - 1) && (field[x][y + 1])) {
					field[x][y + 1] = false;
					logs.push(std::make_pair(x, y + 1));
				}
			}

		}
	}


	std::cout << num << '\n';

	for (int i = 0; i < N; ++i) delete[] field[i];
	delete[] field;
}

 

풀 이

 

• [BaekJoon] 2667번 : 단지 번호 붙이기

[백준] 2667번 : 단지 번호 붙이기와 유사한 문제입니다

단지 번호 붙이기의 경우에는 안에 내용이 몇개 인지도 필요하지만, 이 문제의 경우에는 몇 개의 단지가 있는지만 생각하고 풀면 됩니다. DFS 깊이 기반 탐색을 통하여 구현을 하였습니다.

 

출 력 값

 

 

문 제  출 처

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