음식물 피하기

문제

언어

  • JavaScript

순서도

  1. 음식물이 있는 위치를 기준으로 BFS 탐색
  2. 매 탐색마다 각 음식물의 크기 구하기
  3. 구한 음식물의 크기 중 가장 큰 값 출력

문제 풀이 step 1

  • N x M 크기의 통로가 있고, 통로 중간 중간에 음식물이 위치하고 있습니다.
  • 음식물은 상, 하, 좌, 우 4 개의 방향으로 서로 뭉쳐서 큰 음식물 쓰레기가 됩니다.
  • 통로에서 가장 큰 음식물 쓰레기의 크기를 찾는 문제입니다.

문제 풀이 step 2

  • 우선, 주어진 입력을 이용해서 통로에 음식물을 표시합니다.
  • 통로를 전부 순회하며, 음식물이 있는 위치를 기준으로 BFS 탐색을 수행합니다.
  • 탐색을 수행하며, 음식물이 뭉치게 되었을 때 그 크기를 구합니다.
  • 구한 크기 중에서 가장 큰 값을 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	enqueue(item) {
		this.bucket[++this.rear] = item;
	}

	dequeue() {
		return this.bucket[++this.front];
	}

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

// 4 가지 방향
let dir = [
	[0, 1],
	[0, -1],
	[-1, 0],
	[1, 0],
];

// 불가능한 경로인지 검사하는 함수
const isPossibleRoute = (n, m, x, y) => 0 <= x && x < n && 0 <= y && y < m;

// BFS 탐색 함수
const bfs = (n, m, arr, x, y, depth) => {
	const queue = new Queue();

	arr[x][y] = depth;
	queue.enqueue([x, y]);

	let cnt = 1;
	while (!queue.isEmpty()) {
		const [fx, fy] = queue.dequeue();

		for (let i = 0; i < 4; i++) {
			const [tx, ty] = [fx + dir[i][0], fy + dir[i][1]];

			if (!isPossibleRoute(n, m, tx, ty)) continue;
			if (arr[tx][ty] !== 0) continue;

			// 탐색을 수행하며, 음식물의 크기 갱신
			cnt += 1;
			arr[tx][ty] = depth;
			queue.enqueue([tx, ty]);
		}
	}

	// 구한 음식물의 크기 반환
	return cnt;
};

const solution = (input) => {
	const [n, m, k] = input[0].split(" ").map(Number);
	const arr = Array.from(Array(n), () => Array(m).fill(-1));

	for (let i = 1; i < k + 1; i++) {
		const [x, y] = input[i].split(" ").map(Number);
		arr[x - 1][y - 1] = 0;
	}

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

			// BFS 탐색을 수행하며, 가장 큰 음식물의 크기 구하기
			max = Math.max(max, bfs(n, m, arr, i, j, depth));
			depth += 1;
		}
	}

	return max;
};

console.log(solution(input));