백준 3197 백조의 호수 js

3197번: 백조의 호수

요약하면 다음과 같습니다.

• 하루 간격 물과 접촉한 빙판이 녹습니다.
• 얼음에 막혀 서로 만나지 못하는 백조 두 마리가 만나기 위해 며칠이 지나야 하는지 출력하면 됩니다.

아이디어 탐구.

단순히 생각했을 때 얼음을 하루 녹이고, 백조가 서로 만날 수 있는지 탐색하는 과정을 반복하면 정답을 찾을 수 있습니다.

하지만 호수의 행, 열이 1 ≤ R, C ≤ 1500로 넓기 때문에 매일마다 이전의 과정을 반복하면 시간 초과를 예상할 수 있습니다.

따라서 이전 과정에서 시간을 줄일 수 있는 부분을 살펴보면 아래 이미지와 같이

과정 1. 얼음을 녹이는 과정을 한번의 BFS 과정으로 처리하는 방법을 생각할 수 있습니다.

과정 1.

과정 1. 까지의 풀이 연습이 필요할 경우 토마토 문제를 추천해 드립니다.

 

이어서 얼음을 모두 녹였으니

과정 2. 한번의 BFS 과정으로 백조가 서로 만나는 데까지 며칠이 걸리는지 탐색하고 출력해주면 되겠습니다.

 

결과로 얼음을 녹이는 과정의 BFS와 백조가 서로 만나는 과정의 BFS 각각 한 번으로 정답을 출력할 수 있습니다.

 

풀이. 

다음 풀이는 출력값인 "백조가 서로 만나는데 걸리는 날"을 "비용"으로 치환하여 설명합니다.

과정 1. 은 다음과 같습니다.

1. 하나의 queue에 모든 물의 영역을 담습니다.
2. bfs를 통해 물과 근접한 얼음은 초기 값 1로 갱신해 줍니다. 
   1. 이전에 갱신한 얼음과 근접한 얼음이라면 이전에 갱신한 값에 + 1로 갱신해줍니다.

과정 2. 는 다음과 같습니다.

1. 임의의 백조 하나의 위치를 시작으로 bfs 탐색을 해줍니다.
   1. 이때 백조가 서로 만나는 경로가 돌고 돌아서 만나게 되면 진작 만날 수 있는 비용보다 더 큰 값으로 출력되기 때문에 우선순위 큐를 이용해 비용이 작은 순으로 탐색해줍니다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let R, C;
let lake = [];
let lakeVisited = [];
let swanVisited = [];
const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];
let swanPos = [];
let lakeQueue = [];

// 백조가 서로 만나는데 활용할 최소 힙 함수
function minHeap(Q) {
  this.queue = Q;

  this.enqueue = (arr) => {
    this.queue.push(arr);
    let p = this.queue.length - 1;

    while (p > 1 && this.queue[Math.floor(p / 2)][2] > this.queue[p][2]) {
      let temp = this.queue[Math.floor(p / 2)];
      this.queue[Math.floor(p / 2)] = this.queue[p];
      this.queue[p] = temp;
      p = Math.floor(p / 2);
    }
  };

  this.dequeue = () => {
    if (this.queue.length === 2) return this.queue.pop();
    let removeNum = this.queue[1];
    this.queue[1] = this.queue.pop();
    let p = 1;
    let c = 2;

    while (c < this.queue.length) {
      if (
        c + 1 < this.queue.length &&
        this.queue[c][2] > this.queue[c + 1][2]
      ) {
        c = c + 1;
      }
      if (this.queue[p][2] < this.queue[c][2]) break;
      let temp = this.queue[c];
      this.queue[c] = this.queue[p];
      this.queue[p] = temp;
      p = c;
      c *= 2;
    }

    return removeNum;
  };
}

function meltIce() {
  let index = 0;

  while (lakeQueue.length > index) {
    const [y, x] = lakeQueue[index++];

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

      if (nx >= 0 && ny >= 0 && nx < C && ny < R && !lakeVisited[ny][nx]) {
        // 물의 영역과 근접한 얼음을 
        // 초기 값 1 또는 이전 날에 녹은 얼음에 하루를 더한 값으로 갱신해줍니다.
        if (lake[ny][nx] === "X") {
          if (lake[y][x] === "." || lake[y][x] === "L") {
            lake[ny][nx] = 1;
          } else {
            lake[ny][nx] = lake[y][x] + 1;
          }
        }
        lakeVisited[ny][nx] = true;
        lakeQueue.push([ny, nx]);
      }
    }
  }
}

function swansMeet() {
  const minQ = new minHeap([null]);
  // 초기 queue로 백조 위치와 비용을 0으로 넣어줍니다.
  minQ.enqueue([...swanPos, 0]);
  const [initY, initX] = swanPos;
  swanVisited[initY][initX] = true;

  while (minQ.queue.length > 1) {
    const [y, x, days] = minQ.dequeue();

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

      if (nx >= 0 && ny >= 0 && nx < C && ny < R && !swanVisited[ny][nx]) {
        if (lake[ny][nx] === "L") {
          // 백조를 만났기때문에 비용 출력.
          return days;
        }
        if (lake[ny][nx] === ".") {
          minQ.enqueue([ny, nx, days]);
        } else {
          // 탐색중에 비용이 줄어들 수는 없기때문에 
          // 다음 영역의 비용과 비교하여 최대 값을 queue에 넣어줍니다.
          minQ.enqueue([ny, nx, Math.max(days, lake[ny][nx])]);
        }
        swanVisited[ny][nx] = true;
      }
    }
  }
}

rl.on("line", function (line) {
  if (!R) {
    [R, C] = line.split(" ").map((n) => +n);
    lakeVisited = Array.from({ length: R }, () => Array(C).fill(false));
    swanVisited = Array.from({ length: R }, () => Array(C).fill(false));
  } else {
    lake.push(line.split(""));
    if (lake.length === R) rl.close();
  }
}).on("close", function () {
  for (let i = 0; i < R; i++) {
    for (let j = 0; j < C; j++) {
      // 과정 1.을 해결하기 위해 물의 영역을 하나의 lakeQueue에 담아줍니다.
      if (lake[i][j] === "." || lake[i][j] === "L") {
        lakeQueue.push([i, j]);
      }

	  // 과정 2.에서 필요한 백조의 위치를 미리 받아놓습니다.
      if (lake[i][j] === "L") {
        swanPos = [i, j];
      }
    }
  }

  meltIce(); // 실행 후 lake배열은 과정 1.을 거친 배열로 갱신됩니다. 
  const result = swansMeet();
  console.log(result);

  process.exit();
});