토마토

문제

언어

  • JavaScript

문제 풀이 step 1

  • 이번 문제에는 시작점이 여러개인 부분이 기존의 BFS 문제와 다릅니다.
    • 각 익은 토마토에서 동시에 자신의 주변 토마토에 영향을 주기 때문에 시작점이 여러개인 것입니다.
    • 그래서 BFS 탐색의 초기 queue 에는 익은 토마토 전부 넣어줍니다.
  • 이후로는 똑같이 BFS 탐색을 수행해주면 됩니다.
    • 단, 저는 방문 처리를 방문 시마다 익는 날짜를 기록하는 방식으로 대신했습니다.
  • 이외의 부분은 기존의 BFS 문제와 다른 것은 없습니다.

문제 풀이 step 2

  • 간단한 Queue 를 구현해서 풀었습니다.
  • 왜냐하면, 그냥 배열로 push, shift 하는 방식으로 풀어보니 시간초과가 났습니다.
  • 큐는 배열 형태로 간단하게 enqueue, dequeue, isEmpty 3 개 함수만 추가해서 구현했습니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

// 간단한 큐 구현
class Queue {
	constructor() {
		this.backet = [];
		this.front = -1;
		this.rear = -1;
	}

	enqueue(data) {
		this.backet[++this.front] = data;
	}

	dequeue() {
		if (!this.isEmpty()) return this.backet[++this.rear];
	}

	isEmpty() {
		return this.front === this.rear;
	}
}

class Dot {
	constructor(x, y) {
		this.x = x;
		this.y = y;
	}
}

const BFS = (n, m, arr, queue) => {
	const cx = [0, 0, 1, -1];
	const cy = [1, -1, 0, 0];

	while (!queue.isEmpty()) {
		const from = queue.dequeue();
		const NEXT_MARK = arr[from.x][from.y] + 1;

		for (let i = 0; i < 4; i++) {
			const to = new Dot(from.x + cx[i], from.y + cy[i]);

			if (
				0 <= to.x &&
				to.x < m &&
				0 <= to.y &&
				to.y < n &&
				arr[to.x][to.y] === 0
			) {
				arr[to.x][to.y] = NEXT_MARK;
				queue.enqueue(to);
			}
		}
	}
};

// 익을 때까지의 최소 날짜 세기
const countDays = (n, m, arr) => {
	let count = 0;
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (arr[i][j] === 0) return -1;

			if (count < arr[i][j]) count = arr[i][j];
		}
	}

	return count - 1;
};

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);

	// 입력과 동시에 시작점 찾기
	const arr = [];
	const queue = new Queue();
	for (let i = 1; i < m + 1; i++) {
		arr[i - 1] = input[i].split(" ").map(Number);

		for (let j = 0; j < n; j++) {
			if (arr[i - 1][j] !== 1) continue;

			queue.enqueue(new Dot(i - 1, j));
		}
	}

	BFS(n, m, arr, queue);

	return countDays(n, m, arr);
};

console.log(solution(input));