발행일

99클럽 코테 스터디 12일차 TIL + 오늘의 학습 키워드: 깊이/너비 우선 탐색(DFS/BFS)

99클럽 코테 스터디 12일차 TIL + 오늘의 학습 키워드: 깊이/너비 우선 탐색(DFS/BFS)

이 글은 네이버 블로그에 2025년 3월 7일에 올렸던 것을 그대로 옮겨온 것입니다.

  • 오늘의 회고

  • 어떤 문제가 있었고, 나는 어떤 시도를 했는지

  • 어떻게 해결했는지

  • 무엇을 새롭게 알았는지

  • 내일 학습할 것은 무엇인지

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [M, N, H] = input.shift().split(' ').map(Number);
const dx = [-1, 1, 0, 0, 0, 0];  // 좌,우,상,하,앞,뒤일 때 x좌표
const dy = [0, 0, -1, 1, 0, 0]; // 좌,우,상,하,앞,뒤일 때 y좌표
const dz = [0, 0, 0, 0, -1, 1]; // 좌,우,상,하,앞,뒤일 때 z좌표 (상자 인덱스)
const queue = [];
const boxes = Array.from(Array(H), () => Array.from(Array(N), () => Array.from(Array(M).fill(0))));

// 3차원 배열에 입력값 삽입
for (let i = 0; i < H; i++) {
  for (let j = 0; j < N; j++) {
    boxes[i][j] = input.shift().split(' ').map(Number);
  }
}

let unripeTomato = 0;
for (let i = 0; i < H; i++) {
  for (let j = 0; j < N; j++) {
    for (let k = 0; k < M; k++) {
			// 익지 않은 토마토이면 카운트 증가
      if (boxes[i][j][k] == 0) unripeTomato++;
			// 익은 토마토이면 큐에 담기 (현재 위치 및 걸린 일수 초기값 0)
      if (boxes[i][j][k] == 1) queue.push([i, j, k, 0]);
    }
  }
}

let idx = 0; // 큐 인덱스
let answer = 0; // 걸린 기간(일수) 담을 변수
while (queue.length > idx) {
  const [z, x, y, days] = queue[idx++];

	// 현재 위치 기준 인접한 여섯 곳 탐색할 반복문
  for (let i = 0; i < 6; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];
    const nz = z + dz[i];

		// 해당 위치가 상자(그래프) 범위 밖으로 벗어나지 않았고, 안 익은 토마토이면
    if (nz >= 0 && nz < H && nx >= 0 && nx < N && ny >= 0 && ny < M && !boxes[nz][nx][ny]) {
      boxes[nz][nx][ny] = 1; // 토마토 익힘
      queue.push([nz, nx, ny, days + 1]); // 큐에 해당 위치와 하루 증가한 값 담기
      unripeTomato--; // 안 익은 토마토 개수 감소
    }
  }
  answer = days;
}

// 안 익은 토마토가 있다면 -1 반환, 없으면 걸린 기간(일수) 반환 
console.log(unripeTomato ? -1 : answer);

필수 해시태그: #99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL

image