[백준] JavaScript - 토마토 (7569)

개요

문제 이름: 토마토 (7569)
문제 링크: https://www.acmicpc.net/problem/7569
플랫폼: 백준
알고리즘 분류: BFS
소요 시간: 2시간

 

문제 전문

설명

입출력

문제 풀이

해설

이 문제는 3차원 공간에서 토마토의 익는 시간을 구하는 문제입니다. BFS (Breadth-First Search) 알고리즘을 사용하여 해결할 수 있습니다. BFS는 너비 우선 탐색으로, 시작점에서 가까운 노드부터 차례대로 탐색하는 알고리즘입니다.

 

1. 입력받은 토마토 상자 정보를 3차원 배열로 저장합니다.
2. 익은 토마토의 위치를 큐에 넣고, 방문 표시를 합니다.
3. BFS를 수행하면서, 익은 토마토의 인접한 위치에 있는 익지 않은 토마토를 익게 만들고, 익은 토마토의 위치를 큐에 넣습니다.
4. BFS가 종료되었을 때, 모든 토마토가 익었다면 최소 일수를 출력하고, 익지 않은 토마토가 있다면 -1을 출력합니다.

문제를 접근하는 방식은 위와 같습니다.

 

문제를 요약하면, 3차원 공간에서 익은 토마토를 시작점으로 BFS를 수행하여 모든 토마토가 익을 때까지의 최소 일수를 구하는 것입니다.

 

1. 입력받은 토마토 상자 정보를 1차원 배열로 저장합니다. 이는 3차원 인덱스를 1차원 인덱스로 변환하여 계산을 간단하게 만들기 위함입니다.
2. 익은 토마토의 위치를 큐에 넣고, 방문 표시를 합니다. 이때, 익지 않은 토마토의 개수도 카운트합니다.
3. BFS를 수행하면서, 큐에서 토마토의 위치를 꺼내고, 인접한 6개 방향(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)에 대해 다음을 수행합니다:
   1. 인접한 위치가 상자 범위 내에 있고, 익지 않은 토마토라면 익게 만들고, 큐에 넣고, 방문 표시를 합니다. 익지 않은 토마토의 개수를 감소시킵니다.
4. BFS가 종료되었을 때, 익지 않은 토마토의 개수가 0이라면 최소 일수를 반환하고, 그렇지 않다면 -1을 반환합니다.

상세한 풀이 방식은 위와 같습니다.

 

시도

1차 시도  (실패)

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

const [M, N, H] = input[0].split(" ").map(Number);
const box = input.slice(1).map((line) => line.split(" ").map(Number));

const dx = [-1, 1, 0, 0, 0, 0];
const dy = [0, 0, -1, 1, 0, 0];
const dz = [0, 0, 0, 0, -1, 1];

function bfs() {
	const queue = [];
	let days = 0;

	for (let h = 0; h < H; h++) {
		for (let n = 0; n < N; n++) {
			for (let m = 0; m < M; m++) {
				if (box[h * N + n][m] === 1) {
					queue.push([h, n, m, 0]);
				}
			}
		}
	}

	while (queue.length > 0) {
		const [z, y, x, day] = queue.shift();
		days = Math.max(days, day);

		for (let i = 0; i < 6; i++) {
			const nz = z + dz[i];
			const ny = y + dy[i];
			const nx = x + dx[i];

			if (nz >= 0 && nz < H && ny >= 0 && ny < N && nx >= 0 && nx < M && box[nz * N + ny][nx] === 0) {
				box[nz * N + ny][nx] = 1;
				queue.push([nz, ny, nx, day + 1]);
			}
		}
	}

	return days;
}

function checkAllRipe() {
	for (let h = 0; h < H; h++) {
		for (let n = 0; n < N; n++) {
			if (box[h * N + n].includes(0)) return false;
		}
	}
	return true;
}

const result = bfs();
console.log(checkAllRipe() ? result : -1);

이 코드는 3차원 배열을 사용하여 문제를 해결하려 했습니다. BFS를 수행하면서 익은 토마토의 위치를 큐에 넣고, 인접한 위치에 있는 익지 않은 토마토를 익게 만듭니다. 모든 BFS가 종료된 후, 토마토 상자를 확인하여 모두 익었는지 판별합니다.

 

하지만 이 코드는 시간 초과가 발생합니다. 3차원 배열을 사용하여 인덱스 계산을 하는 과정에서 시간 복잡도가 증가하기 때문입니다.

 

• 시간 복잡도 및 공간 복잡도
  • 시간 복잡도: O(M * N * H)
  • 공간 복잡도: O(M * N * H)

 

2차 시도  (성공)

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

const [M, N, H] = input[0].split(" ").map(Number);
const totalSize = M * N * H;

const box = new Int8Array(totalSize);
let unripeTomatoes = 0;

const queue = [];
const visited = new Set();

for (let i = 0, k = 0; i < H; i++) {
	for (let j = 0; j < N; j++) {
		const line = input[i * N + j + 1].split(" ").map(Number);
		for (let m = 0; m < M; m++, k++) {
			box[k] = line[m];
			if (line[m] === 1) {
				queue.push(k);
				visited.add(k);
			} else if (line[m] === 0) unripeTomatoes++;
		}
	}
}

const directions = [1, -1, M, -M, M * N, -M * N];

function isValid(index, dir) {
	const z = Math.floor(index / (M * N));
	const y = Math.floor((index % (M * N)) / M);
	const x = index % M;

	if (dir === 0 || dir === 1) return x + directions[dir] >= 0 && x + directions[dir] < M;
	if (dir === 2 || dir === 3)
		return y + Math.floor(directions[dir] / M) >= 0 && y + Math.floor(directions[dir] / M) < N;
	return z + Math.floor(directions[dir] / (M * N)) >= 0 && z + Math.floor(directions[dir] / (M * N)) < H;
}

function bfs() {
	let days = -1;
	let queueIndex = 0;

	while (queueIndex < queue.length) {
		const size = queue.length - queueIndex;
		days++;

		for (let i = 0; i < size; i++) {
			const current = queue[queueIndex++];

			for (let dir = 0; dir < 6; dir++) {
				if (isValid(current, dir)) {
					const next = current + directions[dir];
					if (box[next] === 0 && !visited.has(next)) {
						box[next] = 1;
						queue.push(next);
						visited.add(next);
						unripeTomatoes--;
					}
				}
			}
		}
	}

	return unripeTomatoes === 0 ? days : -1;
}

console.log(bfs());

이 코드는 3차원 배열 대신 1차원 배열을 사용하여 문제를 해결합니다. 3차원 인덱스를 1차원 인덱스로 변환하여 계산을 간단하게 만들었습니다.

1. 입력 받기
   1. fs 모듈을 사용하여 표준 입력에서 데이터를 읽어옵니다.
   2. 입력 데이터를 줄 단위로 분리하여 input 배열에 저장합니다.
2. 변수 초기화
   1. 첫 번째 줄에서 M(가로 칸 수), N(세로 칸 수), H(상자 수)를 공백으로 분리하여 숫자로 변환합니다.
   2. totalSize는 전체 토마토 상자의 크기를 계산합니다. (M * N * H)
   3. box 배열은 1차원 배열로, 토마토 상자의 상태를 저장합니다. Int8Array를 사용하여 메모리 효율성을 높입니다.
   4. unripeTomatoes는 익지 않은 토마토의 개수를 저장할 변수입니다.
   5. queue는 BFS에서 사용될 큐이며, 익은 토마토의 위치를 저장합니다.
   6. visited는 방문한 토마토의 위치를 저장할 Set입니다.
3. 토마토 상자 정보 저장
   1. 3중 반복문을 사용하여 입력 데이터를 순회합니다.
   2. 입력 데이터에서 토마토 상자 정보를 읽어와 box 배열에 저장합니다.
   3. 익은 토마토(값이 1)의 위치는 queue에 추가하고, visited Set에 추가합니다.
   4. 익지 않은 토마토(값이 0)의 개수를 unripeTomatoes에 누적합니다.
4. BFS 수행
   1. bfs 함수에서 BFS를 수행합니다.
   2. days는 토마토가 모두 익는 데 걸리는 최소 일수를 저장할 변수입니다.
   3. queueIndex는 큐에서 현재 처리 중인 토마토의 인덱스를 가리킵니다.
   4. 큐에 토마토가 남아있는 동안 반복합니다.
      1. 현재 큐의 크기(queue.length - queueIndex)를 size 변수에 저장합니다.
      2. days를 증가시킵니다.
      3. size만큼 반복하면서...
         1. 큐에서 토마토의 위치(current)를 꺼냅니다.
         2. 인접한 6개 방향에 대해 반복합니다.
            1. isValid 함수를 사용하여 인접한 위치가 유효한지 확인합니다.
            2. 유효한 위치이고, 익지 않은 토마토(값이 0)이며, 방문하지 않은 위치라면:
               1. 해당 위치의 토마토를 익은 상태(값을 1)로 변경합니다.
               2. 해당 위치를 큐에 추가하고, visited Set에 추가합니다.
               3. unripeTomatoes를 감소시킵니다.
5. 결과 반환
   1. BFS가 종료된 후, unripeTomatoes가 0이라면 모든 토마토가 익은 것이므로 days를 반환합니다.
   2. 그렇지 않다면 익지 않은 토마토가 남아있는 것이므로 -1을 반환합니다.
6. 결과 출력
   1. bfs 함수의 반환값을 console.log로 출력합니다.

사용된 주요 메서드

• Array.prototype.map(callback): 배열의 모든 요소에 대해 제공된 함수를 호출하고, 그 결과로 새로운 배열을 생성합니다.
  • input[0].split(" ").map(Number)는 입력의 첫 번째 줄을 공백으로 분리하고, 각 요소를 숫자로 변환한 새로운 배열을 생성합니다.
  • input[i * N + j + 1].split(" ").map(Number)는 입력의 각 줄을 공백으로 분리하고, 각 요소를 숫자로 변환한 새로운 배열을 생성합니다.
• Set.prototype.has(value): Set 객체에 특정 요소가 존재하는지 여부를 판단합니다.
  • if (box[next] === 0 && !visited.has(next))는 다음 위치의 토마토가 익지 않았고, 방문하지 않은 위치인지 확인합니다.
• Set.prototype.add(value): Set 객체에 주어진 값을 추가합니다.
  • visited.add(k)는 현재 위치를 방문 처리합니다.
  • visited.add(next)는 다음 위치를 방문 처리합니다.
• Array.prototype.push(element): 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새로운 길이를 반환합니다.
  • queue.push(k)는 익은 토마토의 위치를 큐에 추가합니다.
  • queue.push(next)는 익은 토마토의 다음 위치를 큐에 추가합니다.
• Math.floor(value): 주어진 숫자 이하의 가장 큰 정수를 반환합니다.
  • const z = Math.floor(index / (M * N))는 1차원 인덱스에서 z 좌표를 계산합니다.
  • const y = Math.floor((index % (M * N)) / M)는 1차원 인덱스에서 y 좌표를 계산합니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(M * N * H)
  • BFS 알고리즘을 사용하여 토마토 상자의 모든 칸을 탐색합니다.
  • 최악의 경우, 모든 토마토가 익지 않은 상태에서 시작하여 모든 칸을 방문해야 합니다.
  • 토마토 상자의 크기가 M * N * H이므로, 시간 복잡도는 O(M * N * H)입니다.
• 공간 복잡도: O(M * N * H)
  • 토마토 상자의 상태를 저장하는 box 배열의 크기는 M * N * H입니다.
  • BFS에 사용되는 큐(queue)와 방문 여부를 저장하는 Set(visited)의 크기는 최악의 경우 토마토 상자의 모든 칸을 저장해야 하므로, O(M * N * H)입니다.
  • 따라서 공간 복잡도는 O(M * N * H)입니다.