[JS][백준]16236_아기 상어

문제 번호

16236번: 아기 상어

 

 

알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 시뮬레이션

 

문제 풀이

 상어 시리즈 문제이다.

BFS에 약간의 구현을 곁들이면 쉽게 풀 수 있다.

 

 우리의 아기 상어는 자신보다 작은 물고기를 먹을 수 있고, 더 큰 물고기는 통과하지 못한다.

문제에서 주어진 먹을 수 있는 물고기의 조건을 확인하여 BFS로 먹을 수 있는 물고기를 찾아보자.

우선적으로 가장 가까운 위치의 물고기를 목표로 하기 때문에 BFS에서 최단거리에 있는 물고기를 발견한다면 더 탐색할 필요는 없다.

 같은거리에 있는 물고기가 여러 마리일 수 있으므로 food라는 배열에 넣어서 return 해줄 것이다.

function BFS(N, map, shark) {
  let food = [];
  let visited = new Array(N).fill(null).map(_ => new Array(N).fill(false));
         // 상 우 하 좌
  let dx = [0, 1, 0, -1];
  let dy = [-1, 0, 1, 0];

  let q = new Queue();
  q.push(shark.x, shark.y, 0);

  let min = Infinity;
  while (q.length()) {
    let cur = q.pop();
    let [curX, curY, curDist] = [cur.x, cur.y, cur.dist]; // 위치와 거리
    if (map[curY][curX] !== 0 && map[curY][curX] < shark.size) {  // 먹을 수 있는 물고기라면.
      if (curDist < min) // 최단거리에 있는 물고기 까지의 최단거리 찾기.
        min = curDist;
      if (curDist <= min) {  // 먹을 수 있는 물고기 후보군 추가.
        food.push({
          x: curX,
          y: curY,
          dist: curDist
        })
      }
    }

    for (let next = 0; next < 4; next++) {
      let [nextX, nextY] = [curX + dx[next], curY + dy[next]];
      if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
      if (!visited[nextY][nextX] && map[nextY][nextX] <= shark.size && curDist < min) {
        visited[nextY][nextX] = true;
        q.push(nextX, nextY, curDist + 1);
      }
    }
  }
  return food;
}
main();

 

 BFS를 통해서 먹을 수 있는 물고기들의 위치를 받아왔으면 문제에서 주어진 조건을 잘 살펴봐서 어떤 물고기를 먹어야 하는지 알아보자.

    let food = BFS(N, map, shark);
    food.sort((a, b) => {      
        if (a.y < b.y) return -1;
        else if (a.y > b.y) return 1;
        else {
          if (a.x < b.x) return -1;
          else if (a.x > b.x) return 1;
          return 0;
        }
      }
  )

 

먹을 물고기를 찾았으면 먹으면 된다.

상어는 자신의 몸집과 같은 수만큼의 물고기를 먹으면 몸집이 한 단계 커진다. 그래서 상어가 커지기 위해서 더 먹어야 하는 물고기의 수를 shark.exp라고 설정했다.

// 3. 먹자.
    if (food.length === 0) // 먹을게 없는경우. 
      return time;
    time += food[0].dist;
    shark.exp--;
    if (shark.exp === 0) {
      shark.size++;
      shark.exp = shark.size;
    }
    [shark.x, shark.y] = [food[0].x, food[0].y];
    map[food[0].y][food[0].x] = 0;

 

전체 코드

class Node {
  constructor(x, y, dist) {
    this.x = x;
    this.y = y;
    this.dist = dist;
    this.next = null;
  }
}
class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  length() {
    return this.size;
  }
  push(x, y, dist) {
    let node = new Node(x, y, dist);
    if (this.size === 0) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
  }
  pop() {
    let temp = this.head;
    if (this.size <= 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
    }
    this.size--;
    return temp;
  }
}
function main() {
  const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
  const N = +input[0];
  let map = input.slice(1).map(_ => _.trim().split(' ').map(Number));

  // shark init.
  let shark = {
    x: 0,
    y: 0,
    size: 2,
    exp: 2
  }
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (map[i][j] === 9) {
        [shark.x, shark.y] = [j, i];
        map[i][j] = 0;
      }
    }
  }

  console.log(sol(N, map, shark));
}
function sol(N, map, shark) {
  /**
 * 맵 최대 400.
 * 먹을 수 있는 물고기가 몇마린지?  최대 399마리.
 * 1. 먹을 수 있는 물고기가 몇마리인지.
 * 2. 여러 마리라면 그 물고기들 까지의 거리를 구한다.(BFS)
 *    2-1 거리가 같다면 문제의 조건을 따른다.
 * 3. 상어의 크기가 변경될때 마다 1번을 다시 구해야한다.
 * 4. 1번에서 더 이상 먹을 수 있는 물고기가 없다고 판명되면 종료한다.
 */
  let time = 0;
  while (1) { 
    // 2.가장 가까운 물고기들.
    let food = BFS(N, map, shark);
    food.sort((a, b) => {      
        if (a.y < b.y) return -1;
        else if (a.y > b.y) return 1;
        else {
          if (a.x < b.x) return -1;
          else if (a.x > b.x) return 1;
          return 0;
        }
      }
  )

    // 3. 먹자.
    if (food.length === 0) // 먹을게 없는경우. 
      return time;
    time += food[0].dist;
    shark.exp--;
    if (shark.exp === 0) {
      shark.size++;
      shark.exp = shark.size;
    }
    [shark.x, shark.y] = [food[0].x, food[0].y];
    map[food[0].y][food[0].x] = 0;
  }

}
function BFS(N, map, shark) {
  let food = [];
  let visited = new Array(N).fill(null).map(_ => new Array(N).fill(false));
         // 상 우 하 좌
  let dx = [0, 1, 0, -1];
  let dy = [-1, 0, 1, 0];

  let q = new Queue();
  q.push(shark.x, shark.y, 0);

  let min = Infinity;
  while (q.length()) {
    let cur = q.pop();
    let [curX, curY, curDist] = [cur.x, cur.y, cur.dist]; // 위치와 거리
    if (map[curY][curX] !== 0 && map[curY][curX] < shark.size) {  // 먹을 수 있는 물고기라면.
      if (curDist < min) // 최단거리에 있는 물고기 까지의 최단거리 찾기.
        min = curDist;
      if (curDist <= min) {  // 먹을 수 있는 물고기 후보군 추가.
        food.push({
          x: curX,
          y: curY,
          dist: curDist
        })
      }
    }

    for (let next = 0; next < 4; next++) {
      let [nextX, nextY] = [curX + dx[next], curY + dy[next]];
      if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
      if (!visited[nextY][nextX] && map[nextY][nextX] <= shark.size && curDist < min) {
        visited[nextY][nextX] = true;
        q.push(nextX, nextY, curDist + 1);
      }
    }
  }
  return food;
}
main();

 

특이사항

 문제를 빠르게 풀진 못한 것 같지만 헤매면서 풀지는 않았다. 길이가 긴 구현 문제라면 천천히 풀더라도 코드를 다시 작성하는 일이 없도록 정확하게 푸는 게 더 중요한 것 같다.