토마토
📚 문제 설명
M * N 의 크기의 창고가 있다.
이 창고에 토마토를 넣어서 보관하는데 토마토는 익은 토마토 주위(상하좌우)로 익기 시작한다고 한다.
이 때, 모든 토마토가 익을 때까지 걸리는 시간을 구하는 문제이다.
예시
2 * 2 의 창고에 [0,0] 에 익은 토마토가 있다고 가정하면 다음과 같은 과정으로 익는다.
따라서 해당 예시에서는 2의 시간동안 전체 토마토가 익기 때문에 결과가 2가 나와야 한다.
👨🏻💻 풀이 과정
이런 맵 전체가 채워지는데까지 걸리는 최단 시간 혹은 목적지까지 가는 최단 거리를 구하는 문제의 경우 너비 우선 탐색 (BFS)를 쓰는 경우가 많다.
그리고 이런 문제의 유형은 아주 전형적인 BFS 문제 유형이라고 볼 수 있다.
그럼 BFS에 대해 확인하기 전에 전체 로직에 대해 설명하면 다음과 같다.
- 상자에서 익은 토마토의 위치를 파악한다.
- 익은 토마토의 위치에서 BFS를 이용해 상자를 익은 토마토로 채워간다.
- BFS를 통해 토마토들을 익게 만든 후, 전체 상자에 있는 토마토들이 익었는지 확인, 상자의 숫자 중 가장 큰 값을 찾아줌.
전체 로직
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let [N, M] = input.shift().split(' ').map(Number);
let Map = input.map(v => v.split(' ').map(Number));
// 익은 토마토를 찾아주는 함수
const FindRotten = (MAP) => {
let Queue = [];
// MAP을 돌면서 익은 토마토 탐색 후, 큐에 삽입
for (let i = 0; i < M; i++) {
for (let j = 0; j < N; j++) {
if (MAP[i][j] === 1) {
Queue.push([i, j]);
}
}
}
return Queue;
};
const BFS = () => {
//생략
}
BFS();
//
// MAP을 확인 후, 만약 0이 발견되면 바로 -1을 return
// 아니라면 MAP에서 가장 큰 값을 리턴.
const Check = (MAP) => {
let max = 0;
for (let i = 0; i < M; i++) {
for (let j = 0; j < N; j++) {
if (MAP[i][j] === 0) return -1;
if (max < MAP[i][j]) max = MAP[i][j];
}
}
return max - 1;
};
console.log(Check(Map));
💡너비 우선 탐색 (Breadth - First - Search)
너비 우선 탐색은 인접한 노드를 먼저 탐색하는 방식으로 깊이 우선 탐색(DFS) 와 함께 언급되는 방식이다.
이렇게 말로 설명해도 크게 와닿지 않기 때문에 트리를 탐색하는 과정을 예시로 들면, 더 이해하기가 좋다.
아래 그림은 1번 노드를 시작점으로 하여 너비 우선 탐색을 진행 했을 때, 탐색되는 순서대로 표현한 그림이다.
너비 우선 탐색은 몇가지 특징이 있는데 그 중에서 가장 중요한 점은 Queue(큐)를 사용한다는 점과 DFS(깊이 우선 탐색)과는 다르게 재귀를 사용하지 않는다는 점이다.
그럼 위의 그림을 예시로 Queue(큐)를 어떻게 사용하는지 보면 다음과 같다.
- 우선 시작점을
Queue에 넣어준다. (큐 :1) - 그 후
Queue에서 있는 1을 확인하고 1번 노드와 인접한 노드들을Queue에 넣어준다. (큐 :2, 3, 4) - 다시 큐에 있는 2를 확인, 2번 노드와 인접한 노드를
Queue에 삽입 (큐 :3, 4, 5, 6) - 그리고
3,4,5,6노드들은 입접한 노드들이 이미 왔던 노드들이다. 따라서Queue에 삽입하지 않는다. (큐 : 비어있음)
이렇게 BFS를 진행하면 탐색 순서는 1 - 2 - 3 - 4 - 5 - 6 이 된다.
(참고 : DFS의 경우 1 - 2 - 5 - 6 - 3 - 4 순으로 탐색하게 된다.)
이제 해당 문제에 사용할 BFS 코드를 보면 다음과 같다.
BFS 코드
const BFS = () => {
// 큐에 익은 토마토의 좌표를 넣어줌
// 시작점들을 넣어주는 과정
let Que = FindRotten(Map);
// 상하 좌우 이동을 위한 변수
let dx = [1, -1, 0, 0];
let dy = [0, 0, 1, -1];
// 원래 Que.shift를 이용했으나, 시간초과가 난다. 따라서 인덱스 번호를 이용하는 것으로 변경
let idx = 0;
// 원래 Que.length만 넣었으나 변경
while (Que.length !== idx) {
// 원래는 Que.shift() 했으나 변경
let [X, Y] = Que[idx];
// 상하좌우 움직였을 때
for (let i = 0; i < dx.length; i++) {
let nextX = X + dx[i];
let nextY = Y + dy[i];
// 상자 크기를 벗어나면 안됨
if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M) {
// 만약 다음 위치의 값이 0이면 이전 값 + 1을 넣어줌
if (Map[nextX][nextY] === 0) {
Map[nextX][nextY] = Map[X][Y] + 1;
Que.push([nextX, nextY]);
}
}
}
// Que의 다음 인덱스를 확인해야하기 때문에
idx++;
}
}전체 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let [N, M] = input.shift().split(' ').map(Number);
let Map = input.map(v => v.split(' ').map(Number));
const FindRotten = (MAP) => {
let Queue = [];
for (let i = 0; i < M; i++) {
for (let j = 0; j < N; j++) {
if (MAP[i][j] === 1) {
Queue.push([i, j]);
}
}
}
return Queue;
};
const BFS = () => {
let Que = FindRotten(Map);
let dx = [1, -1, 0, 0];
let dy = [0, 0, 1, -1];
let idx = 0;
while (Que.length !== idx) {
let [X, Y] = Que[idx];
for (let i = 0; i < dx.length; i++) {
let nextX = X + dx[i];
let nextY = Y + dy[i];
if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M) {
if (Map[nextX][nextY] === 0) {
Map[nextX][nextY] = Map[X][Y] + 1;
Que.push([nextX, nextY]);
}
}
}
idx++;
}
}
BFS();
const Check = (MAP) => {
let max = 0;
for (let i = 0; i < M; i++) {
for (let j = 0; j < N; j++) {
if (MAP[i][j] === 0) return -1;
if (max < MAP[i][j]) max = MAP[i][j];
}
}
return max - 1;
};
console.log(Check(Map));🧐 후기
처음에 Queue에서 shift()를 하며 순서대로 큐에서 값을 뽑아가며 진행했는데 시간 초과가 나게 되었다.
그런데 도저히 모르겠어서 다른분들의 리뷰를 찾아보니 shift()를 써서 그런거라는 사실을 알게 되었고, 바로 변수를 이용해 인덱스 값을 직접 주어서 Queue를 탐색하도록 바꿔주었더니 무사히 통과하게 되었다.
shift() 의 시간 복잡도가 O(n)이라는 사실은 이미 알고 있었고 최근 알고리즘 풀이에서는 최대한 쓰지않으려고 노력했는데, BFS를 오랜만에 풀면서 잠시 잊고 코드를 작성했던 것 같다.
