[백준/Node.js] 3197 백조의 호수

배운 점
- BFS에서 shift() 사용으로 인한 성능 저하(O(n)) => Queue는 직접 구현하자 (O(1))

 

Queue 

지금까지 BFS를 풀며 queue는 다음과 같이 shift()로 사용했었다. 

const queue = [];

queue.push([x, y]);

const [x, y] = queue.shift();

 

그런데 이번엔 시간초과가 떴다.. 왜그런지 알아보자.

성능 영향 분석

1. shift()의 시간 복잡도

• shift()는 배열의 첫 번째 요소를 제거하고, 나머지 모든 요소를 앞으로 한 칸씩 이동시킨다. 이 이동 연산이 배열의 크기만큼 발생하므로 O(n)의 시간 복잡도를 가진다.
• 이는 배열 크기가 커질수록 이 연산이 반복되기 때문에 비효율적이다. 

2. BFS에서 큐를 사용하는 경우

• BFS에서는 큐(FIFO) 자료구조가 매우 중요한데, shift()를 사용해 배열을 큐처럼 사용하면, 매번 맨 앞에서 요소를 제거할 때 O(n)의 시간이 걸리므로, BFS를 실행할 때 매번 배열 크기만큼의 시간이 소요된다. 이로 인해 성능 저하가 크게 발생할 수 있다.

해결: 직접 구현해서 O(1)로 줄이자

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++;
  }

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

  isEmpty() {
    return this.length === 0;
  }
}

 

 이렇게 하면 push()와 pop() 모두 O(1) 시간 복잡도를 가지기 때문에, BFS에서 효율적으로 동작할 수 있다.

 

전체 코드

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++;
  }

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

  isEmpty() {
    return this.length === 0;
  }
}

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

const [R, C] = input.shift().split(" ").map(Number);
const lake = input.map((row) => row.split(""));
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

const visited = Array.from({ length: R }, () => Array(C).fill(false));
const swansVisited = Array.from({ length: R }, () => Array(C).fill(false));
const swans = [];
const waterQueue = new Queue();
const swanQueue = new Queue();
const swanTemp = new Queue();

for (let x = 0; x < R; x++) {
  for (let y = 0; y < C; y++) {
    if (lake[x][y] === "L") {
      swans.push([x, y]);
      lake[x][y] = ".";
      waterQueue.push([x, y]);
    }
    if (lake[x][y] === ".") {
      waterQueue.push([x, y]);
    }
  }
}

swanQueue.push(swans[0]);
swansVisited[swans[0][0]][swans[0][1]] = true;

function meltIce() {
  const newQueue = new Queue();

  while (!waterQueue.isEmpty()) {
    const [x, y] = waterQueue.pop();
    visited[x][y] = true;

    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 || visited[nx][ny]) continue;

      visited[nx][ny] = true;

      if (lake[nx][ny] === "X") {
        lake[nx][ny] = ".";
        newQueue.push([nx, ny]);
      }
    }
  }
  while (!newQueue.isEmpty()) {
    waterQueue.push(newQueue.pop());
  }
}

function swansMeet() {
  while (!swanQueue.isEmpty()) {
    const [x, y] = swanQueue.pop();

    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 || swansVisited[nx][ny])
        continue;

      if (nx === swans[1][0] && ny === swans[1][1]) {
        return true;
      }

      if (lake[nx][ny] === ".") {
        swanQueue.push([nx, ny]);
      } else if (lake[nx][ny] === "X") {
        swanTemp.push([nx, ny]);
      }

      swansVisited[nx][ny] = true;
    }
  }

  while (!swanTemp.isEmpty()) {
    const [x, y] = swanTemp.pop();
    swanQueue.push([x, y]);
  }
  return false;
}

function BFS() {
  let day = 0;

  while (true) {
    if (swansMeet()) {
      return day;
    }

    meltIce();
    day++;
  }
}

console.log(BFS());

 

• 처음에 swans 배열에 백조의 위치들을 저장한다. 이때, 백조는 물 위에 떠있으므로 '.'로 바꿔주고 waterQueue에도 넣어준다. 
• 두 마리 백조가 만날 수 있는지 확인, 만날 수 없다면 얼음을 한 층 녹이고 day를 1 증가시킨다.
• BFS 탐색이 두 번 수행되어야 한다.(얼음을 녹이기 위한 BFS, 두 백조가 만나는지 확인하기 위한 BFS)
• visited로 중복된 탐색을 하지 않게 최적화해야 한다.
• swanTemp라는 임시 큐를 사용해서 얼음에 막힌 백조의 위치를 저장하고, 다음 날 탐색할 수 있도록 처리한다.