[백준 #3197] 백조의 호수, 자바스크립트 풀이

문제 난이도	유형
🏅 플래티넘 5티어	큐, BFS, 시뮬레이션

 

문제

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	21220	4462	2703	19.271%

 

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

 

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는지 계산하는 프로그램을 작성하시오.

 

입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

 

출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

 

예제 입력

8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

예제 출력

2

---

풀이

두 가지 구현부를 나눌 수 있다. 얼음을 녹이는 부분과 백조가 서로 만날 수 있는지 확인하는 부분으로 나누어서 문제를 해결해 나가면 된다. 최악의 경우 1500 x 1500의 맵을 여러 번 BFS 해야 하기 때문에, 최적화를 하지 않는다면 시간 초과나 메모리 초과를 만날 수 있다.

 

현재 맵에서 두 마리 백조가 서로 만날 수 있는지 확인하고, 만날 수 없다면 물과 인접해있는 모든 얼음을 녹인 다음에 day를 증가하면서 진행하면 된다.

 

얼음을 녹이는 부분

function melting(waterQueue, liver, R, C) {
  const next = new Queue();
  while (!waterQueue.isEmpty()) {
    const [x, y] = waterQueue.dequeue();
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
      if (liver[nx][ny] === "X") {
        liver[nx][ny] = ".";
        next.enqueue([nx, ny]);
      }
    }
  }
  return next;
}

얼음을 녹이기 위해서는 처음에 모든 물의 위치가 저장된 큐가 있어야 한다. waterQueue가 비어있을 때까지 순회하면서 사방에 있는 얼음을 녹이면 된다. 중요한 것은 next 큐인데, 과거에 확인한 물 주위는 다시 확인할 필요가 없기 때문에 얼음이었다가 이번에 새로 물이 된 곳들을 다음날에 처리할 물의 위치로 담아서 리턴한다. 즉, next는 다음 melting 함수의 waterQueue가 된다.

 

백조가 서로 만날 수 있는지 확인하는 부분

//if duck found then return false, else then return object(true)
function notFoundDuck(duckQueue, liver, visited, R, C) {
  const next = new Queue();
  while (!duckQueue.isEmpty()) {
    const [x, y] = duckQueue.dequeue();
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
      if (visited[nx][ny]) continue;
      if (liver[nx][ny] === ".") {
        visited[nx][ny] = true;
        duckQueue.enqueue([nx, ny]);
      } else if (liver[nx][ny] === "X") next.enqueue([x, y]);
      else if (liver[nx][ny] === "L") return false;
    }
  }
  return next;
}

이 부분은 많이 어려웠다. 백조를 이동을 최적화를 하는 데 많은 자료도 찾아보고, 실제 집 앞의 하천을 계속 뚫어져라 찾아봤다.  크레이지 아케이드를 통해 원리를 알아보자.

 

출처: 크레이지 아케이드

결론부터 말하자면 백조가 BFS를 하면서 이전에 갔던 길은 다시 가지 않고, 얼음을 만나기 이전 위치를 next 큐에 담아서 다음날부터는 백조가 그 위치에서부터 BFS를 수행한다. 왼쪽 빨간 다오의 영역을 점점 늘려가면서 BFS를 수행하는 것이다. 

출처: 크레이지 아케이드

즉, 위와 같이 얼음을 만나는 동그라미 위치에서부터 다음날 BFS를 시작하면 경로가 최적화된다. 이렇게 하기 위해서 백조의 위치를 담을 수 있는 큐가 하나 있어야 하고, 백조가 방문한 길을 체크하기 위해 2차원 배열도 만들어야 한다. 얼음을 녹이는 부분이 next 큐를 반환해서 다음 waterQueue로 들어온 것처럼, next 큐는 다음 duckQueue로 들어온다.

 

나는 한 마리의 백조만 움직이게 구현했다. 만약 백조가 다른 백조를 찾으면 false를 리턴한다. 왜냐하면 찾지 못하면 queue를 리턴하는데, 자바스크립트에서 object는 항상 true이기 때문에 백조를 찾은 경우에는 false를 리턴하도록 했다.

 

코드

const readline = require("readline");

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

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

rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  const [R, C] = input.shift().split(" ").map(Number);

  solution(
    R,
    C,
    input.map((v) => [...v])
  );

  process.exit();
});

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.queue[this.rear++] = value;
  }
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front++];
    return value;
  }
  isEmpty() {
    return this.front == this.rear;
  }
}

function melting(waterQueue, liver, R, C) {
  const next = new Queue();
  while (!waterQueue.isEmpty()) {
    const [x, y] = waterQueue.dequeue();
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
      if (liver[nx][ny] === "X") {
        liver[nx][ny] = ".";
        next.enqueue([nx, ny]);
      }
    }
  }
  return next;
}

//if duck found then return false, else then return object(true)
function notFoundDuck(duckQueue, liver, visited, R, C) {
  const next = new Queue();
  while (!duckQueue.isEmpty()) {
    const [x, y] = duckQueue.dequeue();
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
      if (visited[nx][ny]) continue;
      if (liver[nx][ny] === ".") {
        visited[nx][ny] = true;
        duckQueue.enqueue([nx, ny]);
      } else if (liver[nx][ny] === "X") next.enqueue([x, y]);
      else if (liver[nx][ny] === "L") return false;
    }
  }
  return next;
}

function solution(R, C, liver) {
  let duckQueue = new Queue();
  let waterQueue = new Queue();
  let isFounded = false;
  let result = 0;
  const visited = Array.from(Array(R), () => Array(C).fill(false));

  //setting
  for (let i = 0; i < R; i++) {
    for (let j = 0; j < C; j++) {
      if (liver[i][j] === ".") waterQueue.enqueue([i, j]);
      else if (!isFounded && liver[i][j] === "L") {
        liver[i][j] = ".";
        visited[i][j] = true;
        isFounded = true;
        waterQueue.enqueue([i, j]);
        duckQueue.enqueue([i, j]);
      } else if (isFounded && liver[i][j] === "L") {
        waterQueue.enqueue([i, j]);
      }
    }
  }

  //play logic
  while (true) {
    duckQueue = notFoundDuck(duckQueue, liver, visited, R, C);
    if (!duckQueue) {
      console.log(result);
      break;
    }
    waterQueue = melting(waterQueue, liver, R, C);
    result++;
  }
}