[백준] BFS 유기농 배추

백준 1012번 BFS 유기농 배추 

 

---

1012번 유기농 배추 풀이

이 문제는 일반적인 BFS 코드에서 약간의 응용을 가미한 코드이다. 

순차적으로 모든 x,y 를 살펴보면서 만약 1이면 그 근처에 있는 1인 구간을 다 탐색한 뒤, 다시 순차적으로 x,y를 탐색하는 구조이다. 

 

이 문제의 특이한 점은 BFS를 테스트케이스로 줘서 초기화 시켜줘야한다는 점이다. 이 부분에서 약간 당황했는데

int board[502][502]; // 값이 1인 곳
bool vis[502][502];	// 방문 여부, 방문 했으면 1 안했으면 0

 

이 부분을 for 문 안에 가져오면 에러가 뜨기 때문에, for문에서 다시 이 값들을 초기화해줘야 했다.

 

for (int i = 0; i < 502; i++) {
	fill(board[i], board[i] + 502, 0);
	fill(vis[i], vis[i] + 502, 0);
}

 

이런식으로 fill 함수를 써서 board와 vis를 초기화해줬다. 

 

이것 외에는 일반적인 BFS로 충분히 풀 수 있다. 

유기농 배추 전체 코드 

#include <iostream>
#include <queue>
using namespace std;
#define X first
#define Y second
int board[502][502];
bool vis[502][502];
int main() {

	int T;
	cin >> T;
	int dx[4] = { 1,0,-1,0 };
	int dy[4] = { 0,1,0,-1 };

	for (int t = 0; t < T; t++) {
		for (int i = 0; i < 502; i++) {
			fill(board[i], board[i] + 502, 0);
			fill(vis[i], vis[i] + 502, 0);
		}
		//cout << "int" << '\n';
		int n, m, k;
		cin >> m >> n;
		cin >> k;
		//cout << m << n << k << '\n';
		int result = 0;
		
		for (int p = 0; p < k; p++) {
			//cout << k << '\n';
			int x, y;
			cin >> x >> y;
			board[x][y] = 1;
		}
		queue<pair<int, int>> Q;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (board[i][j] == 1 && vis[i][j] != 1) {
					Q.push({ i, j });
					result++;
					vis[i][j] = 1;
					//cout << "int" << '\n';
					while (!Q.empty()) {
						pair<int, int> cur = Q.front(); Q.pop();
						//cout << '(' << cur.X << ", " << cur.Y << ") -> ";
						for (int dir = 0; dir < 4; dir++) {
							int nx = cur.X + dx[dir];
							int ny = cur.Y + dy[dir];
							if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
							if (vis[nx][ny] == 1 || board[nx][ny] == 0) continue;
							vis[nx][ny] = 1;
							Q.push({ nx,ny });
						}
					}
				}
			}
		}

		cout << result << '\n';
	}
}