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

오늘은 백준1012번 유기농 배추 문제를 풀어보도록 하자.

BFS, DFS 모두 가능한 문제로 두 가지 방법으로 풀어보았다. 기본적인 BFS, DFS 개념을 습득하기 위해 좋은 문제이다.

문제는 다음과 같다.

                               [접근법]

  1. BFS - 큐를 이용

  2. DFS - 재귀를 이용

                                     [코드]
                                     
                                     ___BFS___
#include <iostream>
#include <queue>
using namespace std;

int map[50][50];
bool visit[50][50];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int cnt = 0, R, C;
struct pos {
	int y;
	int x;
};
queue<pos>Q;

void Init() { //초기화
	for (int i = 0; i < 50; i++) {
		for (int j = 0; j < 50; j++) {
			map[i][j] = 0;
			visit[i][j] = false;
		}
	}
	cnt = 0;
}

bool Inbound(int y, int x) {//경계조건
	if (y >= 0 && y < R && x >= 0 && x < C) {
		return true;
	}
	return false;
}

void cnt_the_worm() {
	while (!Q.empty()) {
		int size_of_Q = Q.size();

		for (int i = 0; i < size_of_Q; i++) {
			int y = Q.front().y;
			int x = Q.front().x;

			Q.pop();

			for (int j = 0; j < 4; j++) {
				int my = y + dir[j][0];
				int mx = x + dir[j][1];

				if (Inbound(my, mx)) {
					if (map[my][mx] == 1 && !visit[my][mx]) {
						visit[my][mx] = true;
						Q.push({ my,mx });
					}
				}
			}
		}
	}
}

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

	int Testcase, num, x, y;

	cin >> Testcase;
	
	while (Testcase--) {
		cin >> C >> R >> num;

		for (int i = 0; i < num; i++) {
			cin >> x >> y;
			map[y][x] = 1;
		}
		
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (map[i][j] == 1 && !visit[i][j]) {
					Q.push({ i,j }); visit[i][j] = true; cnt++;
					cnt_the_worm();
				}
			}
		}
		cout << cnt << '\n';
		Init();
	}
}


                                     ___DFS___
#include <iostream>
using namespace std;

int map[50][50];
bool visit[50][50];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int cnt = 0, R, C;


void Init() { //초기화
	for (int i = 0; i < 50; i++) {
		for (int j = 0; j < 50; j++) {
			map[i][j] = 0;
			visit[i][j] = false;
		}
	}
	cnt = 0;
}

bool Inbound(int y, int x) {//경계조건
	if (y >= 0 && y < R && x >= 0 && x < C) {
		return true;
	}
	return false;
}

void cnt_the_worm(int y, int x) {
	visit[y][x] = true;	

	for (int i = 0; i < 4; i++) {
		int my = y + dir[i][0];
		int mx = x + dir[i][1];

		if (Inbound(my, mx)) {
			if (map[my][mx] == 1 && !visit[my][mx]) {
				cnt_the_worm(my, mx);
			}
		}
	}
}

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

	int Testcase, num, x, y;

	cin >> Testcase;
	
	while (Testcase--) {
		cin >> C >> R >> num;

		for (int i = 0; i < num; i++) {
			cin >> x >> y;
			map[y][x] = 1;
		}
		
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (map[i][j] == 1 && !visit[i][j]) {
					cnt++;
					cnt_the_worm(i,j);
				}
			}
		}
		cout << cnt << '\n';
		Init();
	}
}