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

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

1012번: 유기농 배추

 

문제 분석

배추를 보호하기 위해 인접해있는 배추 무리마다 배추흰지렁이를 배치하기 위해서 배추흰지렁이가 얼마나 필요한지를 구하는 문제이다. 배추는 상하좌우 네 방향으로 붙어있는 경우에 인접한 것이다. 인접한 배추 무리가 몇 개인지 구하면 된다. 너비우선탐색(BFS)를 통해 문제를 풀 수 있다.

코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

#define MAX 50

int map[MAX][MAX];
queue<pair<int, int>> q;
int n, m, k;
bool visited[MAX][MAX];
int ans;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void reset(){
	for(int i=0; i<50; i++){
		for(int j=0; j<50; j++){
			map[i][j] = 0;
			visited[i][j] = false;
		}
	}
	ans = 0;
}

void bfs(int x, int y){
	visited[x][y] = true;
	q.push(make_pair(x, y));
	
	while(!q.empty()){
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for(int i=0; i<4; i++){
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx>=0 && ny>=0 && nx<n && ny<m){
				if(map[nx][ny]==1 && !visited[nx][ny]){
					visited[nx][ny] = true;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}	
}

int main(){
	int t;
	cin>>t;
	for(int p=0; p<t; p++){
		reset();
		
		cin>>m>>n>>k;
		
		for(int i=0; i<k; i++){
			int a, b;
			cin>>a>>b;
			map[b][a] = 1;
		}
		
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				if(map[i][j]==1 && !visited[i][j]){
					bfs(i, j);
					ans++;
				}
			}
		}
		
		cout<<ans<<"\n";
	}
	
	return 0;
}

 

문제 풀이

1. 테스트케이스의 개수 t를 입력받고 반복문으로 t번동안 아래 과정을 반복한다.
2. reset함수로 배추밭을 입력받을 map과 방문했었는지 여부를 저장할 visited를 초기화한다.
3. 배추밭의 크기인 m, n과 배추의 개수 k를 입력받고 배추의 위치들을 입력받아 map의 해당 위치를 1로 설정한다.
4. 배추밭에서 배추가 심어진 곳을 찾아야 하므로 이중 반복문을 통해 모든 위치를 보도록 하고 배추가 있고 방분한 적이 없을 때에는 현재 위치를 인자로 bfs함수를 실행한 후 답이 될 ans값을 1 증가시킨다.
5. bfs함수에서는 이미 방문한 곳을 다시 방문하지 않도록 하기 위해서 visited를 조정한다. 인자 x, y는 현재 위치이므로 visited[x][y]를 true로 설정하고 x, y를 pair로 만들어 큐 q에 push한다. 그 후 q가 비지 않는 동안, 즉 더 이상 조건에 충족하는 위치가 없을 때까지, q의 첫 번째 값들을 저장하고 pop한 후, 반복문을 통해 상하좌우 네 방향을 모두 방문하여 조건을 만족하면 해당 위치의 visited를 true로 설정하고 q에 push하도록 한다.
6. 이러면 ans는 bfs가 실행될 때마다, 즉 배추 무리를 찾을 때마다 증가하게 되므로 ans를 출력하면 된다.