[백준 1012] 유기농 배추 cpp

문제
NxM 크기의 땅에 배추가 심어져있으면 1, 빈 칸이면 0으로 표시하였다. 배추흰지렁이를 배추에 두면 해충으로부터 보호를 할 수 있으며 배추흰지렁이는 상하좌우 네 방향으로 움직여 인접한 배추도 보호할 수 있다. 이때 최소 몇 마리의 배추흰지렁이를 사용하여 배추를 보호할 수 있는지 구하라.

입력
첫째 줄에 테스트 케이스가 입력된다.
각 테스트 케이스의 첫쨰 줄에는 가로길이 M과 세로 길이 N(1이상 50이하)이 주어진다. 이후 배추가 심어져 있는 위치의 개수 K가 입력된다. 
그 다음 K 줄에는 배추의 위치가 입력된다.

출력
최소로 필요한 배추흰지렁이 마리 수를 출력한다.

---

접근

배추흰지렁이를 어떤 배추에 놓았을 때 배추흰지렁이는 상하좌우로 이동할 수 있다. 따라서 이 배추의 상하좌우에 있는 배추도 보호할 수 있게된다.

배추흰지렁이를 최소로 놓기위해서 상하좌우로 모여있는 배추에 놓으면 된다.

BFS를 통해 인접한 배추를 검사하도록 한다. 여기서 BFS를 실행한만큼 배추흰지렁이의 마리 수가 될 것이다.

 

구현

전역변수를 다음과 같이 선언해주었다. map의 경우 BFS에서 한 번 방문한 곳을 표시하도록 하기 위함이다. 또한 dir은 상하좌우를 탐색하고, RangeCheck는 해당 위치가 맵 안에 포함된 것인지를 판단한다.

const int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };

int N, M,K;
int map[50][50];

bool RangeCheck(int y, int x) {
	return(y >= 0 && y < N) && (x >= 0 && x < M);
}

 

각 테스트 케이스마다 가로길이, 세로길이, 배추의 개수를 입력받고, 배추의 위치에 1을 대입한다.

int  count = 0;
		
		cin >> M >> N >> K;
		for (int i = 0; i < K; i++) {
			int x, y;
			cin >> x >> y;
			map[y][x] = 1;
		}

 

NxM의 맵을 탐색하여 1이나오면 BFS 탐색을 진행한다. 해당 좌표를 BFS에 넘겨주고 배추흰마리의 마리수를 증가시킨다.

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j]==1) {
                	//배추흰마리 증가시킨다.
					count++;
					BFS(i, j);
				}
			}
		}

 

아래의 코드는 해당위치의 상하좌우를 탐색하여 배추를 찾아 2로 바꿔준다. 이는 중복으로 탐색하지 않도록 방지하는 것이다. 여기서 BFS는 배추흰마리를 놓고 배추흰마리가 보호할 수 있는 범위를 2로 표시하는 것이다.

void BFS(int y, int x) {
	queue<pair<int, int>> q;
	q.push({ y, x });
	map[y][x] = 2;

	while (!q.empty()) {
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ny = cy + dir[d][0];
			int nx = cx + dir[d][1];
			if (RangeCheck(ny, nx) && map[ny][nx] == 1) {
				map[ny][nx] = 2;
				q.push({ ny,nx });
			}
		}
	}
}

 

 

최종적으로 BFS를 몇 번 실행했는지 계산하여 최종해르 출력한다.

---

전체 코드

#include "pch.h"
#include <iostream>
#include<algorithm>
#include <vector>
#include<queue>
using namespace std;

const int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };

int N, M,K;
int map[50][50];

bool RangeCheck(int y, int x) {
	return(y >= 0 && y < N) && (x >= 0 && x < M);
}

void BFS(int y, int x) {
	queue<pair<int, int>> q;
	q.push({ y, x });
	map[y][x] = 2;

	while (!q.empty()) {
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ny = cy + dir[d][0];
			int nx = cx + dir[d][1];
			if (RangeCheck(ny, nx) && map[ny][nx] == 1) {
				map[ny][nx] = 2;
				q.push({ ny,nx });
			}
		}
	}
}
int main()
{
	int test_case;
	cin >> test_case;

	while (test_case--) {
		int  count = 0;
		
		cin >> M >> N >> K;
		for (int i = 0; i < K; i++) {
			int x, y;
			cin >> x >> y;
			map[y][x] = 1;
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j]==1) {
					count++;
					BFS(i, j);
				}
			}
		}

		cout << count<< endl;
	}
	return 0;
}