[백준][bfs] 2573 빙산 NodeJs 구현

     

목차

 

 

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

문제

 

문제 구현 방향

빙산이 녹을 때 따로 대상을 저장해 놓았다가 나중에 한꺼번에 녹이는 것만 주의해 주면 된다.

그 이후에 빙산의 조각 여부는 flag를 통해 쉽게 탐색할 수 있다. 이때 bfs를 써주자

 

부분 메서드 구현

 

빙산 탐색용 메서드

function searching(x, y) {
  if (board[y][x] === 0) return;
  let cnt = 0;
  for (let i = 0; i < 4; i++) {
    let nx = x + dx[i];
    let ny = y + dy[i];
    if (nx < 0 || nx > M - 1 || ny < 0 || ny > N - 1) continue;
    if (board[ny][nx] === 0) cnt++;
  }
  queue.push([x, y, cnt]);
}

 

빙산 녹이는 메서드

function melting() {
  for (let [x, y, cnt] of queue) {
    board[y][x] = Math.max(0, board[y][x] - cnt);
  }
  queue = [];
}

 

빙산 조각 체크 메서드

function bfs(startX, startY, visit) {
  let q = [];
  visit[startY][startX] = 1;
  q.push([startX, startY]);
  while (q.length) {
    let [x, y] = q.shift();
    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (nx < 0 || nx > M - 1 || ny < 0 || ny > N - 1) continue;
      if (visit[ny][nx] || board[ny][nx] === 0) continue;
      q.push([nx, ny]);
      visit[ny][nx] = 1;
    }
  }
}

function checking() {
  let flag = 0;
  let visit = Array.from({ length: N }, () => Array(M).fill(0));
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (!visit[i][j] && board[i][j] !== 0) {
        if (flag >= 1) {
          return flag;
        }
        flag++;
        bfs(j, i, visit);
      }
    }
  }

  return 0;
}

 

모든 빙산이 녹았을 시 확인용 메서드

function allIcing() {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (board[i][j] != 0) {
        return 0;
      }
    }
  }
  return 1;
}

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let [N, M] = input[0].trim().split(" ").map(Number);
let idx = 1;
let board = [];
let queue = [];
let year = 0;
let dx = [0, 1, -1, 0];
let dy = [1, 0, 0, -1];

while (idx < input.length) {
  let t = input[idx].trim().split(" ").map(Number);
  board.push(t);
  idx++;
}

function searching(x, y) {
  if (board[y][x] === 0) return;
  let cnt = 0;
  for (let i = 0; i < 4; i++) {
    let nx = x + dx[i];
    let ny = y + dy[i];
    if (nx < 0 || nx > M - 1 || ny < 0 || ny > N - 1) continue;
    if (board[ny][nx] === 0) cnt++;
  }
  queue.push([x, y, cnt]);
}

function melting() {
  for (let [x, y, cnt] of queue) {
    board[y][x] = Math.max(0, board[y][x] - cnt);
  }
  queue = [];
}
function allIcing() {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (board[i][j] != 0) {
        return 0;
      }
    }
  }
  return 1;
}

function bfs(startX, startY, visit) {
  let q = [];
  visit[startY][startX] = 1;
  q.push([startX, startY]);
  while (q.length) {
    let [x, y] = q.shift();
    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (nx < 0 || nx > M - 1 || ny < 0 || ny > N - 1) continue;
      if (visit[ny][nx] || board[ny][nx] === 0) continue;
      q.push([nx, ny]);
      visit[ny][nx] = 1;
    }
  }
}

function checking() {
  let flag = 0;
  let visit = Array.from({ length: N }, () => Array(M).fill(0));
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (!visit[i][j] && board[i][j] !== 0) {
        if (flag >= 1) {
          return flag;
        }
        flag++;
        bfs(j, i, visit);
      }
    }
  }

  return 0;
}
if (checking()) {
  console.log(0);
  return;
}

while (true) {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      searching(j, i);
    }
  }

  melting();

  if (allIcing()) {
    console.log(0);
    return;
  }

  year++;
  if (checking()) {
    console.log(year);
    return;
  }
}