Home / 알고리즘 / BFS

토마토 백준 7569번

11/13/2024
#알고리즘#BFS

문제

링크

이해

3차원 상자에 담긴 토마토들이 익어가는 과정을 시뮬레이션 하는 것.

  1. 익은 토마토는 하루가 지나면 주위의 익지 않은 토마토를 익게 만든다.
  2. 주위(인접한)의 토마토는 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향을 의미한다.
  3. 모든 토마토가 익는데 걸리는 최소 일수를 구해야 한다.

해결

전체 코드

const BAEAKJOONFILE = "/dev/stdin";
const VSCODEFILE = "./coding/example.txt";

const fs = require('fs');
const input = fs.readFileSync(VSCODEFILE).toString().trim().split('\n');

const [M, N, H] = input[0].split(' ').map(Number);
const box = [];
const queue = [];
let unripeTomatoes = 0;

for (let h = 0; h < H; h++) {
	const floor = [];
	for (let n = 0; n < N; n++) {
		const row = input[1 + h * N + n].split(' ').map(Number);
		floor.push(row);
	
	for (let m = 0; m < M; m++) {
		if (row[m] === 1) queue.push([h, n, m, 0]);
		else if (row[m] === 0) unripeTomatoes++;
		}
	}
	box.push(floor);
}

const directions = [
	[0, 0, 1], [0, 0, -1], [0, 1, 0], [0, -1, 0], [1, 0, 0], [-1, 0, 0]
];

let maxDays = 0;
let queueIndex = 0;

while (queueIndex < queue.length && unripeTomatoes > 0) {
	const [h, n, m, days] = queue[queueIndex++];
	for (let i = 0; i < 6; i++) {
		const nh = h + directions[i][0];
		const nn = n + directions[i][1];
		const nm = m + directions[i][2];
		
		if (nh >= 0 && nh < H && nn >= 0 && nn < N && nm >= 0 && nm < M && box[nh][nn][nm] === 0) {
			box[nh][nn][nm] = 1;
			queue.push([nh, nn, nm, days + 1]);
			unripeTomatoes--;
			maxDays = days + 1;
		}
	}
}

console.log(unripeTomatoes === 0 ? maxDays : -1);

부분 설명

입력

const fs = require('fs');
const input = fs.readFileSync(VSCODEFILE).toString().trim().split('\n');

const [M, N, H] = input[0].split(' ').map(Number);
  • 파일에서 입력을 읽어 온다. 첫 줄에서 상자의 가로(M), 세로(N), 높이(H)를 가져온다.

토마토 상태 파악하기

const box = [];
const queue = [];
let unripeTomatoes = 0;

for (let h = 0; h < H; h++) {
	const floor = [];
	for (let n = 0; n < N; n++) {
		const row = input[1 + h * N + n].split(' ').map(Number);
		floor.push(row);
	
	for (let m = 0; m < M; m++) {
		if (row[m] === 1) queue.push([h, n, m, 0]);
		else if (row[m] === 0) unripeTomatoes++;
		}
	}
	box.push(floor);
}
  • 문자열로 된 배열을 숫자 형태로 변환하면서 3차원 배열로 생성
  • 만약 토마토가 익었다면(1이라면) 큐에 넣기, 큐의 마지막은 날짜(days)가 됨.
  • 아니고 만약 토마토가 안 익었다면(0이라면) 안 익은 토마토 변수의 값을 1 증가

토마토 익히기

const directions = [
	[0, 0, 1], [0, 0, -1], [0, 1, 0], [0, -1, 0], [1, 0, 0], [-1, 0, 0]
];

let maxDays = 0;
let queueIndex = 0;

while (queueIndex < queue.length && unripeTomatoes > 0) {
	const [h, n, m, days] = queue[queueIndex++];
	for (let i = 0; i < 6; i++) {
		const nh = h + directions[i][0];
		const nn = n + directions[i][1];
		const nm = m + directions[i][2];
		
		if (nh >= 0 && nh < H && nn >= 0 && nn < N && nm >= 0 && nm < M && box[nh][nn][nm] === 0) {
			box[nh][nn][nm] = 1;
			queue.push([nh, nn, nm, days + 1]);
			unripeTomatoes--;
			maxDays = days + 1;
		}
	}
}

BFS(너비 우선 탐색)를 사용해 토마토가 익어가는 과정을 시뮬레이션

  • 큐에서 익은 토마토를 하나씩 꺼내서 주변 6방향 확인
  • 안 익은 토마토를 발견하면 익힌 후 큐에 넣기
  • 위 과정 반복하며 최대 일수 갱신

특이사항

시간 초과

현재 코드말고 이전 코드로 했을 때 시간 초과가 났었다.

토마토의 익힘 정도

토마토상태파악하기 부분의 코드를 전에는 3차원 배열을 만드는 로직과 토마토의 익힘 정도 찾는 로직을 따로 for문을 사용해 처리 했다. 아마 시간초과에 유의미한 차이가 있을 것 같아 한 번에 배열과 토마토의 익힘 정도를 구분하는 로직을 모두 처리하기로 한다. 이를 통해 불필요한 반복은 줄이고 실행 시간은 단축시킨다.

큐 구현

const [h, n, m, days] = queue[queueIndex++]; // 이 부분을
const [h, n, m, days] = queue.shift(); // 이렇게 했었다.

이전의 코드와 비교하면 다음과 같이 차이가 난다고 한다.

  • shift 연산의 시간 복잡도는 O(n)
  • 인덱스를 사용하여 큐를 구현하면 O(1) 이라고 한다.
Shift와 인덱스의 시간 차이
  1. shift 연산(Array.prototype.shift):
    • shift 연산은 배열의 첫 번째 요소를 제거하고 반환한다.
    • 이 연산은 O(n) 시간 복잡도를 가진다, 이유는:
      • 첫 번째 요소를 제거한 후 나머지 모든 요소를 한 칸씩 앞으로 이동시키기 때문이다.
    • 따라서 배열의 크기가 클수록 이 연산은 더 많은 시간이 걸리게 된다.
  2. 인덱스를 사용한 큐 구현:
    • 배열을 그대로 두고 인덱스만 이동시킨다.
    • 큐에서 요소를 꺼낼 때마다 인덱스를 1 증가시키기만 하면 된다.
    • 이 연산은 O(1) 시간 복잡도를 가진다. 단순히 인덱스 값만 변경하기 때문이다.

결론적으로, 맨 앞의 값을 꺼내오는 것은 동일하지만, 그 과정에서 발생하는 내부 연산의 복잡도 차이로 인해 성능 차이가 발생한다. 따라서 큐를 구현할 때는 가능한 인덱스 기반의 접근 방식을 사용하는 것이 효율적이라 한다.

블로그 내 관련 문서

참고 자료

출처 :

  • AI가 그렇다고 함

댓글을 불러오는 중...