BOJ - 1012번_유기농 배추

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력하는 프로그램 작성하기

  • 배추흰지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다.
  • 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있다.
  • 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다.


풀이

배추흰지렁이가 있는 지점부터 큐에 넣은 후 BFS를 돈다. 새롭게 BFS를 시작할 때마다 count해준다.


소스코드

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

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int board[55][55];
int vis[55][55];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	
	while(T--) {
		int cnt = 0;
		queue<pair<int,int>> q;
		int M, N, K;
		cin >> M >> N >> K;
		
		for(int i=0; i<N; i++) {
			fill(board[i], board[i]+M, 0);
			fill(vis[i], vis[i]+M, 0);
		}
		while(K--) {
			int X, Y;
			cin >> Y >> X;
			board[X][Y]++;		
		}
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(!board[i][j] || vis[i][j]) continue;
				cnt++;
				vis[i][j] = 1;
				q.push({i,j});
				
				while(!q.empty()) {
					auto cur = q.front();
					q.pop();
					for(int l=0; l<4; l++) {
						int nx = cur.first + dx[l];
						int ny = cur.second + dy[l];
						if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
						if(!board[nx][ny] || vis[nx][ny]) continue;
						vis[nx][ny] = 1;
						q.push({nx,ny});
					}
				}		
			}
		}
		cout << cnt << "\n";
	}
}