[JavaScript/구현] 백준 골드 3 : 16236 - 아기 상어

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

---

📌 작성한 코드 

// 16236
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
let [sx, sy] = [0, 0];
const board = input.map((str, i) => {
    const temp = str.split(" ").map(Number);
    temp.forEach((val, j) => {
        if (val === 9) {
            sx = i;
            sy = j;
        }
    });

    return temp;
});

board[sx][sy] = 0;

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

const bfs = (a, b, cur) => {
    const visited = Array.from({ length: N }, () => new Array(N).fill(false));
    const queue = [];
    queue.push([a, b, 0]);

    const temp = [];
    let standard = Infinity;

    let idx = 0;
    while (queue.length > idx) {
        const [x, y, count] = queue[idx++];

        if (board[x][y] !== 0 && board[x][y] < cur) {
            temp.push([x, y, count]);
            if (standard === Infinity) standard = count;
        }

        if (standard < count) break;

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

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (!visited[nx][ny] && board[nx][ny] <= cur) {
                visited[nx][ny] = true;
                queue.push([nx, ny, count + 1]);
            }
        }
    }

    if (temp.length > 0) {
        temp.sort((a, b) => a[2] - b[2] || a[0] - b[0] || a[1] - b[1]);
        return temp[0];
    } else {
        return false;
    }
};

let time = 0;
let sizeCount = 0;
let [x, y, size] = [sx, sy, 2];

while (true) {
    const temp = bfs(x, y, size);
    if (temp === false) break;

    const [nx, ny, count] = temp;
    time += count;
    x = nx;
    y = ny;
    sizeCount += 1;

    board[x][y] = 0;

    if (sizeCount === size) {
        size += 1;
        sizeCount = 0;
    }
}

console.log(time);

 

📌 설명 

💡 문제의 컨셉 설명

아기 상어가 이동하면서 자신보다 작은 물고기를 먹을 수 있고, 물고기를 현재 크기에 해당하는 개수만큼 먹으면 크기가 증가한다. 이러한 특성을 이용해서 아기상어는 이동하면서 물고기를 잡아먹을 건데, 더 이상 필드 안에 자신보다 작은 물고기가 없으면 먹는 것을 그만두고 엄마 상어를 호출해야 한다. 

-> 이 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지를 구하는 프로그램을 작성해야 한다.

 

💡 아기 상어의 움직임 규칙

0. (초기 세팅) 아기 상어의 초기 위치는 9이고, 1~6까지의 숫자는 다른 물고기의 크기이다.

1. 아기 상어는 자신보다 작은 물고기만 잡아먹을 수 있고, 물고기가 없거나 자신보다 작거나 같은 물고기가 있는 곳으로만 이동할 수 있다. 

- 자신이랑 크기가 같은 물고기는 잡아먹을 수는 있지만 해당 위치로 이동은 가능하다.

2. 먹을 수 있는 물고기 중에서 가장 거리가 가깝고(1순위), 가장 위에 위치하고(2순위), 가장 왼쪽에 위치하는 물고기를 잡아먹는다. 

- 먹을 수 있는 물고기가 1마리라면 당연하게 그 물고기를 먹어야 하고, 여러개가 존재하면 해당 우선순위에 맞는 물고기 1마리를 잡아먹는다. 

 

💡 아기 상어의 이동 로직

필자는 해당 문제를 해결하기 위해 bfs를 사용하여 최단 거리를 구하는 방식을 사용하였다. 

1. 현재 상어의 위치에서 bfs를 사용하여 현재 위치에서 먹을 수 있는 물고기 중 가장 가까이 있는 물고기를 찾는다. 

2. 가장 가까운 물고기가 여러개라면 그 중 우선순위에 맞는 물고기를 먹는다.

3. 상어 자리를 먹은 물고기 자리로 업데이트 하고 bfs를 반복한다.

4. bfs를 돌렸는데도 먹을 수 있는 물고기가 없다면 더이상 이동할 필요가 없으므로 엄마 상어를 부른다(탐색을 종료한다)

 

💡 주의할 점!

1. 초기 상어의 위치가 9인데, 상어를 위치시킨 후에 해당 위치를 그대로 두면 9라서 해당 부분을 우회해서 가는 문제가 발생한다. 0으로 만들어줘야 한다.

2. bfs를 돌 때 첫번째 물고기를 찾은 후에 해당 물고기와 같은 거리에 있는 물고기만 찾는 것이 효율적이다. 

- 첫번째로 찾은 물고기의 거리가 3이라면, 최단 거리가 3이 되므로 3거리에 있는 상어보다 작은 물고기들을 수집한다. 

3. 상어의 크기만큼 물고기를 먹으면 상어가 성장하게 되는데, 이때 먹은 물고기는 초기화 된다. 다시 상어의 크기만큼 먹어야 한다.

- 초기 상어의 크기 2 -> 물고기 2개먹음 -> 3으로 성장 -> 이전에 먹은 2개 초기화, 따라서 1개 먹으면 3개가 되는게 아니라 다시 3개 먹어야 한다.

 

💡 구현

1. 상어의 초기 위치를 찾는다.

- 0으로 만들어주는 것을 잊지말고 꼭 하기. 

const N = Number(input.shift());
let [sx, sy] = [0, 0];
const board = input.map((str, i) => {
    const temp = str.split(" ").map(Number);
    temp.forEach((val, j) => {
        if (val === 9) {
            sx = i;
            sy = j;
        }
    });

    return temp;
});

board[sx][sy] = 0;

2. bfs를 구현한다.

- 상하좌우가 범위를 벗어나지 않고, 이동 가능한 위치(상어보다 작은 값)라면 해당 위치로 이동한다.

- 최단 거리에 위치한 (먹을 수 있는) 물고기만 찾는다. 최단 거리를 저장하고 해당 값보다 거리가 커지면 루프를 빠져나온다.

const bfs = (a, b, cur) => {
    const visited = Array.from({ length: N }, () => new Array(N).fill(false));
    const queue = [];
    queue.push([a, b, 0]);

    const temp = [];
    let standard = Infinity;

    let idx = 0;
    while (queue.length > idx) {
        const [x, y, count] = queue[idx++];

        if (board[x][y] !== 0 && board[x][y] < cur) { // 상어보다 작은 물고기만 먹을 수 있음 (0은 물고기 없음이니까 제외)
            temp.push([x, y, count]);
            if (standard === Infinity) standard = count; // 첫번째 물고기까지의 거리(최단 거리) 저장
        }

        if (standard < count) break; // 최단 거리보다 크면 필요없으니까 루프 끝내기

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

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (!visited[nx][ny] && board[nx][ny] <= cur) { // 방문한적 없고, 상어보다 작거나 같은 곳으로만 이동 가능
                visited[nx][ny] = true;
                queue.push([nx, ny, count + 1]);
            }
        }
    }
};

3. 먹으려는 물고기를 선정한다.

- 우선순위에 맞게 정렬한다. (1순위 : 최단 거리, 2순위 : 가장 위쪽, 3순위 : 가장 왼쪽) 

- 정렬한 물고기 중 맨 첫번째 물고기를 먹는다.

if (temp.length > 0) {
        temp.sort((a, b) => a[2] - b[2] || a[0] - b[0] || a[1] - b[1]);
        return temp[0];
    } else {
        return false;
}

4. bfs를 돌다가 더이상 먹을 물고기가 없으면 프로그램을 종료한다.

- bfs를 돈 후에 이동한 거리만큼 총 시간에 더해준다. (1초에 1칸씩 움직이기 때문)

- bfs 리턴값이 있으면 물고기를 먹은 것이기 때문에 먹은 물고기 개수를 증가시킨다.

- 먹은 물고기의 위치로 상어를 이동시킨다.

- 먹은 물고기가 상어의 크기와 같아지면 성장 시킨다. (물고기 개수도 초기화)

let time = 0;
let sizeCount = 0;
let [x, y, size] = [sx, sy, 2];

while (true) {
    const temp = bfs(x, y, size);
    if (temp === false) break;

    const [nx, ny, count] = temp;
    time += count;
    x = nx;
    y = ny;
    sizeCount += 1;

    board[x][y] = 0;

    if (sizeCount === size) {
        size += 1;
        sizeCount = 0;
    }
}

✅ 성공