[JS/백준]{BFS}(16236) 아기 상어

문제 설명

개인적으로 이 문제는 너무 어려워서 다른 분들을 코드를 엄청 많이 참고한 코드이다.

엄청 새로운 방법은 사용하신 분이 계셔서 해당 코드로 첫번쨰로 풀었고

나중에 다시한번 다른 코드들을 참고해서 혼자 풀어본 코드 총 2개의 방법으로 풀었다.

for문으로 1 ~ n*n 까지의 최대로 이동할수 있는 거리만큼 실행해준다. 즉 i가 거리이다.

지나갈수 있으면 지나가는 경로를 nextQ로 모두 넣어준다 그중 잡아먹을수 있는 물고기가 있을경우

canEat 배열안에 추가해준다. while문이 다 끝난후 canEat배열안에 먹을수 있는 물고기가 있으면

가까운 좌측 상단을 기준에 가장 가까운 물고기를 잡아먹고 무게증가 및 map에 상어 위치를 변경해준다.

만약 잡아먹을 물고기가 없다면 그대로 return후 총 시간을 출력해준다.

풀이 코드

신기하게 푸신 다른분의 코드

function sort(array) {
  return array.sort((a, b) => {
    if (a[0] !== b[0]) {
      return b[0] - a[0];
    }
    return b[1] - a[1];
  });
}

function bfs(map, start, weight, eatCnt) {
  const visited = Array.from(Array(n), () => Array(n).fill(false));
  let queue = [start];
  [x, y] = start;
  visited[x][y] = true;
  map[x][y] = 0;

  for (let i = 1; i < n * n; i++) {
    const nextQ = [];
    const canEat = [];
    while (queue.length) {
      [x, y] = queue.shift();
      for (let k = 0; k < 4; k++) {
        const nx = x + dx[k];
        const ny = y + dy[k];
        if (nx >= n || nx < 0 || ny >= n || ny < 0) {
          continue;
        }

        if (!visited[nx][ny] && map[nx][ny] <= weight) {
          nextQ.push([nx, ny]);
          visited[nx][ny] = true;
          if (map[nx][ny] < weight && map[nx][ny] !== 0) {
            canEat.push([nx, ny]);
          }
        }
      }
    }

    if (canEat.length) {
      const eatFishIndex = sort(canEat);
      [x, y] = eatFishIndex.at(-1);
      map[x][y] = 9;
      eatCnt++;
      if (eatCnt === weight) {
        eatCnt = 0;
        weight++;
      }
      return { next: [x, y], length: i, eatCnt, weight };
    }

    if (!nextQ.length) {
      return { length: 0 };
    }

    queue = [...nextQ];
  }
}

function solution() {
  let weight = 2;
  let start;
  let eatCnt = 0;
  let time = 0;

  const map = input.slice(1).map((str) => str.split(" ").map(Number));

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (map[i][j] === 9) {
        start = [i, j];
      }
    }
  }

  while (true) {
    const obj = bfs(map, start, weight, eatCnt);
    if (obj.length === 0) {
      console.log(time);
      return;
    }
    time += obj.length;
    start = obj.next;
    weight = obj.weight;
    eatCnt = obj.eatCnt;
  }
}

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

const n = +input[0];
const dx = [1, -1, 0, 0];
const dy = [0, 0, -1, 1];

solution();

나중에 다시 풀어본 코드

function sort(array) {
  return array.sort((a, b) => {
    // 2번째 값이 똑같고 0번쨰 값이 똑같으면 1번째 값을 기준으로 내림차순 정렬
    if (a[2] === b[2]) {
      if (a[0] === b[0]) {
        return b[1] - a[1];
      }
      return b[0] - a[0];
      // 2번째 값이 다르면 2번쨰 값으로 내림차순 정렬
    } else {
      return b[2] - a[2];
    }
  });
}

function bfs(map, start, weight) {
  const visited = Array.from(Array(n), () => Array(n).fill(false));
  const distance = Array.from(Array(n), () => Array(n).fill(0));
  let queue = [start];
  [x, y] = start;
  visited[x][y] = true;
  map[x][y] = 0;
  let canEatArr = [];

  while (queue.length) {
    const [curX, curY] = queue.shift();
    for (let k = 0; k < 4; k++) {
      let nx = curX + dx[k];
      let ny = curY + dy[k];

      if (0 <= nx && 0 <= ny && nx < n && ny < n && !visited[nx][ny]) {
        if (map[nx][ny] <= weight) {
          queue.push([nx, ny]);
          visited[nx][ny] = true;
          distance[nx][ny] = distance[curX][curY] + 1;
          if (map[nx][ny] < weight && map[nx][ny] !== 0) {
            canEatArr.push([nx, ny, distance[nx][ny]]);
          }
        }
      }
    }
  }
  return canEatArr;
}

function solution() {
  let weight = 2;
  let start = [0, 0];
  let eatCnt = 0;
  let time = 0;

  const map = input.slice(1).map((str) => str.split(" ").map(Number));

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (map[i][j] === 9) {
        start = [i, j];
      }
    }
  }

  while (true) {
    const canEatArr = bfs(map, start, weight);

    if (canEatArr.length === 0) {
      console.log(time);
      return;
    }
    const sortCanEatArr = sort(canEatArr);
    const [nx, ny, distance] = sortCanEatArr.at(-1);

    time += distance;
    start = [nx, ny];
    eatCnt++;

    if (eatCnt === weight) {
      eatCnt = 0;
      weight++;
    }
  }
}

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

const n = +input[0];
const dx = [1, -1, 0, 0];
const dy = [0, 0, -1, 1];

solution();