[백준] 16236 아기 상어(Javascript)

문제

BOJ16236_아기 상어

요구사항

먹을 수 있는 모든 물고기를 먹었을 때 몇 초 걸리는지 출력

• 상어의 크기 > 물고기의 크기
  먹을 수 있고, 지나갈 수 있음
• 상어의 크기 === 물고기의 크기
  지나갈 수만 있음
• 상어의 크기 < 물고기의 크기
  먹을 수 없고, 지나갈 수도 없음
  
  
• 먹을 수 있는 물고기의 수 === 0
  종료
• 먹을 수 있는 물고기의 수 >= 1
  가장 가까이 있으면서 가장 위에있고 가장 왼쪽에 있는 물고기 먹으러감

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const map = input.slice(1).map((e) => e.split(' ').map(Number));
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const shark = {
    size: 2, // 초기 상어의 크기
    eat: 0, // 먹은 물고기 수
};

// 상어의 시작 위치 찾기
for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
        if (map[i][j] === 9) {
            shark.pos = [i, j];
            map[i][j] = 0;
        }
    }
}

let answer = 0;

while (true) {
    const [y, x] = shark.pos;
    const count = bfs(y, x, 0);
    if (count === 0) break;
}
console.log(answer);

function bfs(y, x, time) {
    const visited = Array.from(Array(N), () => Array(N).fill(0));
    const queue = [[y, x, time]];
    visited[y][x] = 1;
    let front = 0;
    const fish = [];
    while (queue.length > front) {
        const [y, x, time] = queue[front++];
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[ny][nx]) {
                // 먹을 수 있는 물고기
                if (map[ny][nx] && shark.size > map[ny][nx]) fish.push([ny, nx, time + 1]);
                // 상어의 사이즈보다 작거나 같을 경우 방문
                if (shark.size >= map[ny][nx]) {
                    queue.push([ny, nx, time + 1]);
                }
                visited[ny][nx] = 1;
            }
        }
    }
    if (fish.length) {
        fish.sort((a, b) => {
            if (a[2] !== b[2]) return a[2] - b[2]; // time
            else if (a[0] !== b[0]) return a[0] - b[0]; // y
            else return a[1] - b[1]; // x
        });

        eat(...fish[0]);
    }
    return fish.length;
}

function eat(y, x, time) {
    map[y][x] = 0;
    shark.eat += 1;
    // 크기 증가
    if (shark.eat === shark.size) {
        shark.size += 1;
        shark.eat = 0;
    }
    shark.pos = [y, x];
    answer += time; // 이동 횟수
}

접근법

• 먹을 수 있는 물고기 중에 상어의 위치에서 가장 가까우면서 가장 위쪽에 있고 가장 왼쪽에 있는 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 없을 경우 종료
• 필요한 기능
  • 상어 위치 구하기
  • 정렬(거리,y좌표,x좌표)
  • 먹을 수 있는 물고기 판별

상어 위치 구하기

• 상어의 위치를 저장해야 한다. 또한 상어의 크기와, 상어가 먹은 물고기의 수도 저장해놔야 하기 때문에 객체 리터럴을 사용하여 저장한다.

const shark = {
    size: 2, // 초기 상어의 크기
    eat: 0, // 먹은 물고기 수
};
// 상어의 시작 위치 찾기
for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
        if (map[i][j] === 9) {
            shark.pos = [i, j];
            map[i][j] = 0;
        }
    }
}

먹을 수 있는 물고기 판별

• 먹을 수 있는 물고기 정의하기
  • 상어의 현재 크기보다 작은 물고기
  • 상어보다 작은 물고기의 위치로 갈 수 있어야 함

    3
    1 1 1
    3 3 1
    9 3 1

    입력이 위와 같을 경우 상어보다 큰 물고기가 주변을 둘러싸고 있어서 이동할 수 없으므로 해당 경우에는 먹을 수 있는 물고기가 없다고 판별해야 한다.
• BFS로 상어의 위치부터 출발해서 상,하,좌,우를 확인하며 먹을 수 있는 방문할 수 있는 위치는 모두 방문한다.

function bfs(y, x, time) {
    const visited = Array.from(Array(N), () => Array(N).fill(0));
    const queue = [[y, x, time]];
    visited[y][x] = 1;
    let front = 0;
    while (queue.length > front) {
        const [y, x, time] = queue[front++];
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[ny][nx]) {
                // 상어의 사이즈보다 작거나 같을 경우 방문
                if (shark.size >= map[ny][nx]) {
                    queue.push([ny, nx, time + 1]);
                }
              	// 상어의 사이즈보다 큰 경우도 방문처리는 해줌
                visited[ny][nx] = 1;
            }
        }
    }
}

• 먹을 수 있는 물고기(0이 아니면서 상어의 크기보다 값이 작은 곳)에 대한 정보를 배열에 따로 저장해둔다. (거리, y좌표, x좌표)

function bfs(y, x, time) {
  	...
    const fish = [];
    while (queue.length > front) {
        ...
            if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[ny][nx]) {
                // 먹을 수 있는 물고기
                if (map[ny][nx] && shark.size > map[ny][nx]) fish.push([ny, nx, time + 1]);
                ...
            }
        }
    }
}

• BFS 탐색이 종료되었을 때, 위 배열의 길이가 0이라면 먹을 수 있는 물고기가 없는 것이므로 종료한다. 길이가 0이 아니라면 배열을 1.거리, 2.y좌표, 3.x좌표 순으로 오름차순 정렬하면 가장 가깝고, 가장 위에있으며 가장 왼쪽에 있는 물고기가 배열의 첫 번째 인덱스에 위치한다. 따라서 첫 번째 인덱스에 있는 물고기를 먹으면 된다.

function bfs(y, x, time) {
  	...
    while (queue.length > front) {
        ...
    }
    if (fish.length) {
        fish.sort((a, b) => {
            if (a[2] !== b[2]) return a[2] - b[2]; // time
            else if (a[0] !== b[0]) return a[0] - b[0]; // y
            else return a[1] - b[1]; // x
        });
        eat(...fish[0]);
    }
    return fish.length;
}    

물고기 먹기

• 물고기를 먹으면 해당 칸은 빈칸이 된다.

function eat(y, x, time) {
    map[y][x] = 0;
}

• 상어가 먹은 물고기의 수가 증가하고, 먹은 물고기의 수가 현재 크기와 일치할 경우 상어의 크기는 1증가한다. (먹은 물고기의 수 초기화)

function eat(y, x, time) {
    ...
    shark.eat += 1;
    // 크기 증가
    if (shark.eat === shark.size) {
        shark.size += 1;
        shark.eat = 0;
    }
}

• 상어 위치 이동 및 이동 시간 누적

function eat(y, x, time) {
    ...
    shark.pos = [y, x];
    answer += time; // 이동 횟수
}