AJ

안녕하세요

3 분 소요

[BFS] 백조의 호수


시간 제한 메모리 제한
1초 256MB

문제

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

호수는 행이 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’은 백조가 있는 공간으로 나타낸다.


출력 :

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


예제 입력 :

4 11
..XXX...X..
.X.XXX...L.
....XXX..X.
X.L..XXX...


예제 출력 :

2


풀이

BFS 문제, 얼음이 녹는 좌표를 찍을 때와 백조가 이동 가능한 좌표를 찍을 때, 2번 탐색을 해야한다. 최대 1500 * 1500 인 맵이 나오므로, 매번 새로 탐색하면 시간초과로 통과하지 못한다. 최적화를 위한 핵심은 다음과 같다.

  • 이전에 탐색이 중지된 지점에서 탐색을 시작한다.
  • 백조 이동가능 좌표 swanQ, 다음 탐색지점(새로 얼음이 녹은 곳) 저장하는 swanTemp, 녹은 좌표 저장하는 waterQ 가 필요하며, swanQ, swanTemp 순환시킨다.


class Node {
  constructor(item) {
    this.item = item;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(item) {
    const node = new Node(item);
    if (this.head == null) {
      this.head = node;
    } else {
      this.tail.next = node;
    }

    this.tail = node;
    this.length += 1;
  }

  pop() {
    const popItem = this.head;
    this.head = this.head.next;
    this.length -= 1;
    return popItem.item;
  }
}

const input = require("fs")
  .readFileSync("./dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [N, M] = input.shift().split(" ").map(Number);
let lake = input.map((v) => v.trim().split(""));

function solve() {
  const dx = [0, 0, -1, 1];
  const dy = [-1, 1, 0, 0];
  let waterQ = new Queue();
  const swan = [];

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (lake[i][j] == ".") {
        waterQ.push([i, j]);
      } else if (lake[i][j] == "L") {
        swan.push([i, j]);
        lake[i][j] = ".";
        waterQ.push([i, j]);
      }
    }
  }

  let days = 0;
  let visited = Array.from(Array(N), () => Array(M).fill(false));
  const [sx, sy] = swan[0];
  const [ex, ey] = swan[1];
  let swanQ = new Queue();
  const swanTemp = [];
  swanQ.push([sx, sy]);
  visited[sx][sy] = true;

  while (true) {
    while (swanQ.length > 0) {
      const [x, y] = swanQ.pop();
      for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx == ex && ny == ey) {
          return days;
        } else if (nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny]) {
          if (lake[nx][ny] == ".") {
            swanQ.push([nx, ny]);
          } else {
            swanTemp.push([nx, ny]);
          }
          visited[nx][ny] = true;
        }
      }
    }

    while (swanTemp.length > 0) {
      const [x, y] = swanTemp.shift();
      swanQ.push([x, y]);
    }

    // 백조가 만나지 못했을 때 얼음을 녹인다
    const L = waterQ.length;
    for (let l = 0; l < L; l++) {
      const [x, y] = waterQ.pop();
      for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < N && ny < M && lake[nx][ny] == "X") {
          waterQ.push([nx, ny]);
          lake[nx][ny] = ".";
        }
      }
    }
    days++;
  }
}

console.log(solve());




맨 위로

참고