백준 1012번 - 유기농 배추

1012번: 유기농 배추 (acmicpc.net)

1012번: 유기농 배추

한나는 배추 농사를 하는데, 농약을 쓰지 않고 배추를 잘 재배하기 위해서는 해충으로 부터 배추를 보호해야한다.

배추흰지렁이가 해충을 잡아먹기 때문에 해충으로부터 배추를 도와주는데, 이 해충은 상하좌우 네방향에 다른 배추가 있으면 이동을할 수 있다.

 

하지만 안타깝게도 한나의 밭은 고르지 못해서 배추가 군데군데 심어져있는데 .. 이 배추들을 해충으로부터 보호하기위해  필요한 배추흰지렁이의 최소의 수를 출력하는 문제다.

 

#include<iostream>
#include<queue>
#include<utility>
using namespace std;

//배추밭
int field[51][51];
//방문 확인용 배열
int vis[51][51];

//상하 좌우 탐색을 도와주는 배열
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

int testcase;

//배추밭 세로,가로,배추의 수
int n, m ,l;

//배추 좌표받을 변수
int x, y;

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

	cin >> testcase;

	while (testcase--)
	{
		int cnt = 0;
		queue<pair<int, int>> Q;
		
        //입력받는 순서 주의
		cin >> m >> n >> l;
		
        //밭, 방문 배열 0으로 초기화
		for (int i = 0; i < n; i++)
		{
			fill(field[i], field[i] + m, 0);
			fill(vis[i], vis[i] + m, 0);
		}
		
        //배추 좌표 입력받기(x,y의 순서 주의)
		for(int i=0;i<l;i++)
		{
			cin >> y >> x;
			field[x][y] = 1;
		}
        
		//전체 밭 탐색을 위한 이중 포문 시작
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				//방문 했거나 배추가 없는 곳이면 컨티뉴
				if (field[i][j] == 0 || vis[i][j] == 1) continue;

				//탐색의 시작점 = 필요한 벌레의 수
				cnt++;
				Q.push({ i,j });
				vis[i][j] = 1;

				while (!Q.empty())
				{
					auto cur = Q.front(); Q.pop();
					for (int i = 0; i < 4; i++)
					{
						int dirX = cur.first + dx[i];
						int dirY = cur.second + dy[i];

						//인덱스를 넘었으면 컨티뉴
						if (dirX < 0 || dirY < 0 || dirX >=n || dirY >= m) continue;
						//방문 했거나 배추가 없는 곳이면 컨티뉴
						if (vis[dirX][dirY] == 1 || field[dirX][dirY] == 0) continue;
						
						vis[dirX][dirY] = 1;
						Q.push({ dirX,dirY });

					}
				}
			}
		}
		cout << cnt << '\n';
	}


	return 0;
}

1. 테스트케이스를 입력받아서 테스트 케이스만큼 while문을 돌려주었다.

 

2. 입력을 (밭의 가로 크기, 세로 크기, 밭의 배추 갯수) 순서대로 입력받는다.

 

3. 테스트케이스가 1번이라면 굳이 0으로 초기화 시켜줄 필요가 없지만, 테스트 케이스만큼 반복하기 때문에 밭과 방문확인용 배열을 다 0으로 초기화 시켜 주었다.

 

4. 이제 밭의 배추 갯수만큼 배추의 좌표를 입력받아서 field 변수( 밭 배열)에 채워주는 반복문을 도는데,  2차원 배열은 [행][열] 로 입력해주어야 하는데 좌표를 [열][행]으로 입력받게 해서 y , x 순으로 입력받고 배열 [x] [y] 에 넣어주었다.

 

5. cnt 변수를 미리 선언해두고 이중 for문을 돌면서 배열의 전체 탐색을 시작하는데, 이미 방문 했거나 배추가 없는곳이 아니라면 탐색을 시작, cnt를 +1 해주고 bfs를 돌며 상하좌우를 탐색했다.

(★ 배추가 있는 한 그룹에서 bfs를 끝내고 나면 그 그룹은 이미 방문표시가 다 되어있을테니, 이중 for문을 시작할때마다 더해지는 cnt가 필요한 흰지렁이의 최소 갯수이다.)

 

6. cnt 변수를 출력해주고 테스트케이스가 남아있다면 이 과정을 반복한다.

 

 

엄청 높은 난이도의 문제는 아니지만 bfs문제를 처음으로 힌트, 남의 코드를 보지않고 맞추니 감개무량하다.