[백준][Node.js] 1012번 : 유기농 배추

 

 

 

Algorithm

-  유기농 배추 -

 

---

 

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다.

농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다.

이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다.

특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.

(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)

 

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다.

배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

 

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.

(0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)

 

입출력 예시

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

 

문제 풀기

const readline = require("readline");
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});
let problemCount = 0; //문제 개수
let arrInfo = []; // 가로세로와 배추정보
let inputIndex = 0; // input안 위치 설정
let untilIndex = 0; // 고정되어야 하는 인덱스
let input = [];
let graph = [];
let visited = [];
let result = [];
let count = 0;
rl.on("line", function (line) {
	if (problemCount === 0) problemCount = Number(line.toString());
	else if (line.toString().split(" ").length === 3) {
		arrInfo.push(
			line
				.toString()
				.split(" ")
				.map((el) => Number(el))
		);
	} else {
		input.push(
			line
				.toString()
				.split(" ")
				.map((el) => Number(el))
		);
	}
}).on("close", function () {
	for (let i = 0; i < problemCount; i++) {
		count = 0;
		solution(arrInfo[i]);
	}
	console.log(result.join("\n"));
	process.exit();
});

let solution = (problem) => {
	graph = []; // 초기화
	visited = []; // 초기화
	graph = Array.from(Array(problem[1]), () => Array(problem[0]).fill(0));
	visited = Array.from(Array(problem[1]), () => Array(problem[0]).fill(false));
	for (let i = inputIndex; i < inputIndex + problem[2]; i++) {
		graph[input[i][1]][input[i][0]] = 1;
	}

	let BFS = (x, y) => {
		let dy = [0, 0, -1, 1];
		let dx = [-1, 1, 0, 0];
		let queue = [];

		visited[x][y] = true;
		queue.push([x, y]);

		while (queue.length) {
			let [mx, my] = queue.shift();

			for (let i = 0; i < 4; i++) {
				let xx = mx + dx[i];
				let yy = my + dy[i];

				if (0 <= xx && xx < problem[1] && 0 <= yy && yy < problem[0]) {
					if (graph[xx][yy] === 1 && visited[xx][yy] === false) {
						visited[xx][yy] = true;
						queue.push([xx, yy]);
					}
				}
			}
		}
		return;
	};
	for (let i = untilIndex; i < untilIndex + problem[2]; i++) {
		if (visited[input[i][1]][input[i][0]] === false) {
			BFS(input[i][1], input[i][0]);
			count++;
		}
		inputIndex++;
	}
	untilIndex = inputIndex;
	result.push(count);
	return;
};