Node.js) 백준 18809번: Gaaaaaaaaaarden

 

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

18809번: Gaaaaaaaaaarden

 

class Node {
	constructor(item) {
		this.item = item;
		this.next = null;
	}
}

class Queue {
	constructor() {
		this.head = null;
		this.tail = null;
		this.length = 0;
	}

	push(item) {
		const node = new Node(item);
		if (this.head == null) {
			this.head = node;
		} else {
			this.tail.next = node;
		}

		this.tail = node;
		this.length += 1;
	}

	pop() {
		const popItem = this.head;
		this.head = this.head.next;
		this.length -= 1;
		return popItem.item;
	}
}

const fs = require('fs');
let input = fs
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.trim().split(' ').map(Number));
const [N, M, G, R] = input.shift();

const empty = [];

const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];
let max = 0;
// 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양액을 뿌릴 수 있는 땅
// => -1은 호수, 0은 땅
for (let i = 0; i < N; i++) {
	for (let j = 0; j < M; j++) {
		// 배양액 뿌릴 수 있는 곳 찾기
		if (input[i][j] == 2) {
			empty.push([i, j]);
		}
		// 배양액이 퍼질 수 있는 곳은 0으로
		if (input[i][j] == 2 || input[i][j] == 1) {
			input[i][j] = 0;
		} else if (input[i][j] == 0) {
			// 배양액이 퍼질 수 없는 곳은 -1로
			input[i][j] = -1;
		}
	}
}

//배양액 뿌릴 수 있는 곳 중에서 R+G 만큼 구하기
const seed = [];
for (let i = 0; i < 1 << empty.length; i++) {
	// console.log(i.toString(2));
	let bits = i;
	let cnt = 0;
	while (bits > 0) {
		if (bits & 1) cnt++;
		bits >>= 1;
	}
	if (cnt == R + G) {
		seed.push(i);
	}
}

seed.forEach((v) => {
	for (let i = 0; i < v; i++) {
		let temp = i;
		let cnt = 0;
		while (temp > 0) {
			if (temp & 1) cnt++;
			temp >>= 1;
		}
		// 배양액 뿌릴 수 있는 곳 중에서 R이랑 G 나눠서 구하기
		if (cnt == G) {
			const g = i;
			const r = v ^ i;
			const gr = g | r;

			if (v == gr) {
				// console.log('=========================================');
				// console.log(v.toString(2).padStart(empty.length, '0'));
				// console.log(g.toString(2).padStart(empty.length, '0'));
				// console.log(r.toString(2).padStart(empty.length, '0'));

				// 초록 배양액의 위치
				const greenQ = new Queue();

				// 빨간 배양액의 위치
				const redQ = new Queue();

				// 빨간 배양액이 이미 뿌려진 지점 확인
				let visited = Array.from(Array(N), () => Array(M).fill(false));

				// 초록 배양액은 땅에 그리면서 확인
				let board = input.map((v) => [...v]);

				// 배양액이 뿌려진 시점
				let time = 1;
				//꽃이 핀 횟수
				let cnt = 0;

				g.toString(2)
					.padStart(empty.length, '0')
					.split('')
					.forEach((v, i) => {
						if (v === '1') {
							const [x, y] = empty[i];
							greenQ.push(empty[i]);
							// 최초 초록 배양액이 뿌려진곳 표시하기
							board[x][y] = time;
						}
					});
				r.toString(2)
					.padStart(empty.length, '0')
					.split('')
					.forEach((v, i) => {
						if (v === '1') {
							const [x, y] = empty[i];
							redQ.push(empty[i]);
							// 최초 빨간 배양액이 뿌려진곳 표시하기
							visited[x][y] = true;
						}
					});

				// 배양액이 퍼질 수 없을 때까지
				while (greenQ.length > 0 && redQ.length > 0) {
					time++;

					// 초록 배양액 뿌리기
					const GL = greenQ.length;
					for (let s = 0; s < GL; s++) {
						const [x, y] = greenQ.pop();

						// Infinity는 꽃이 핀 땅
						if (board[x][y] == Infinity) continue;

						for (let k = 0; k < 4; k++) {
							const nx = x + dx[k];
							const ny = y + dy[k];
							if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;

							// 아직 초록 배양액이 퍼지지 않는 곳
							if (board[nx][ny] == 0) {
								board[nx][ny] = time;
								greenQ.push([nx, ny]);
							}
						}
					}

					//빨간 배양액 뿌리기
					const RL = redQ.length;
					for (let s = 0; s < RL; s++) {
						const [x, y] = redQ.pop();
						for (let k = 0; k < 4; k++) {
							const nx = x + dx[k];
							const ny = y + dy[k];
							if (nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny])
								continue;

							//같은 시점에 초록배양액과 만났을 경우
							if (board[nx][ny] == time) {
								// 꽃을 피운다.
								board[nx][ny] = Infinity;
								cnt++;
							} else if (board[nx][ny] != -1) {
								redQ.push([nx, ny]);
							}
							visited[nx][ny] = true;
						}
					}
				}
				if (cnt > max) max = cnt;
			}
		}
	}
});
console.log(max);