[BOJ] 1012 - 유기농 배추

안녕하세요.

여행벌입니다.

---

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

[알고리즘설계]

BFS 탐색을 하면서 탐색한 공간은 2로 바꿔주고, BFS탐색을 시행한 횟수를 출력합니다.

#include<iostream>
#include<queue>

using namespace std;

int map[50][50];
void BFS(int, int,int, int);

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

	int t;
	cin >> t;
	while (t--) {
		for (int i = 0; i < 50; i++)
			for (int j = 0; j < 50; j++)
				map[i][j] = 0;
		int row, column, k, x, y, count = 0;
		cin >> row >> column >> k;
		for (int i = 0; i < k; i++) {
			cin >> x >> y;
			map[x][y] = 1;
		}
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < column; j++) {
				if (map[i][j] == 1){
					BFS(i, j, row, column);
					count++;
				}
			}
		}
		cout << count << '\n';
	}
}

void BFS(int i, int j, int row, int column) {
	int x_dir[4] = { -1, 0, 1, 0 };
	int y_dir[4] = { 0, 1 , 0 , -1 };
	queue<int> x;
	queue<int> y;
	x.push(i);
	y.push(j);
	map[i][j] = 2;
	while (!x.empty()) {
		int x1 = x.front();
		int y1 = y.front();
		x.pop(), y.pop();
		for (int k = 0; k < 4; k++) {
			int next_x = x1 + x_dir[k];
			int next_y = y1 + y_dir[k];
			if (0 <= next_x && next_x < row && 0 <= next_y && next_y < column && map[next_x][next_y] == 1) {
				x.push(next_x);
				y.push(next_y);
				map[next_x][next_y] = 2;
			}
		}
	}
	return;
}

---

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.