[BOJ] 1584 게임 (node.js)

BOJ 문제 1584번의 풀이 과정을 작성한 게시글입니다.

 

링크

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

 

문제

세준이는 위험한 지역에서 탈출하는 게임을 하고 있다. 이 게임에는 세준이가 들어갈 수 없는 죽음의 구역이 있고, 들어가서 한 번 움직일 때 마다 생명이 1씩 소모되는 위험한 구역이 있다. 그리고, 자유롭게 생명의 위협없이 움직일 수 있는 안전한 구역이 있다. (안전한 구역은 죽음의 구역과 위험한 구역을 제외한 나머지 이다.)

세준이는 (0, 0)에서 출발해서 (500, 500)으로 가야 한다. 세준이는 위, 아래, 오른쪽, 왼쪽으로만 이동할 수 있다. 현재 세준이는 (0, 0)에 있다. 그리고, 게임 판을 벗어날 수는 없다.

세준이가 (0, 0)에서 (500, 500)으로 갈 때 잃는 생명의 최솟값을 구하는 프로그램을 작성하시오.

 

풀이 과정

틀린 접근법 : bfs

구해야하는 것은 세준이가 (0,0) ~ (500,500)까지 이동할 때 잃는 생명의 최솟값이다.

지역의 타입은 [죽음의 구역, 위험한 구역, 안전한 구역]이 있고, 전체 지역의 크기는 500x500이다.

 

전체를 방문해도 500x500만큼 방문할 것이기 때문에 bfs로 가능한 풀이라고 생각했고,

bfs를 돌리면서 죽음의 구역은 들어가지 않고 위험한 구역에 들어갈 때는 생명을 잃는 수를 늘리면서 탐색했다. 

 

그러나 3%에서 틀렸습니다가 떴다.

해결법이 떠오르지 않아 다른 사람의 풀이를 참고했다.

 

맞는 접근법 : 0-1 bfs (혹은 다익스트라)

이 문제는 0-1 BFS로 풀거나 다익스트라로 접근해야 한다.

우선 로직을 설명하기 전에 0-1 BFS가 어떤 알고리즘인지를 먼저 설명하겠다.

 

0-1 BFS 알고리즘

그래프의 가중치가 0 또는 1일 때 그래프에서 최단 경로를 찾고자 할 때 사용하는 알고리즘

 

만약 다익스트라를 가지고 최단 경로를 찾으면 O(ElogV)의 시간복잡도가 소요되지만, 0-1 BFS 알고리즘을 통해 O(V+E)로 최적화할 수 있기 때문에 사용된다.

 

참고로, 모든 그래프에서 쓸 수 있는게 아니라 가중치가 0 또는 1일 때만 사용할 수 있는 특수한 알고리즘이라는 것에 유의한다.

 

그렇다면 가중치가 0 또는 1이라는게 무슨 말일까?

이 말은 간선의 가중치가 총 2가지 타입만을 가진다는 것을 의미한다.

 

예를 들어 간선의 가중치가 [1, 2] 2개의 타입이라고 할 때, 최종적으로 구하는 목표가 가중치를 최소로 하는 경로라고 해보자.

그렇다면 다익스트라로 구하면 항상 가중치가 1인 노드만을 먼저 방문하게 되지만, bfs를 통해 탐색한다면 항상 가중치가 작은 노드가 앞으로 오게 하기 위해서는 큐를 매번 정렬해야 한다.

 

예를 들어 큐에 [2, 2, 2]가 있고, 새로 방문할 후보에 1이 들어오게 되면, 큐는 [2, 2, 2, 1]이 될 것이다.

이때 큐를 오름차순으로 정렬하지 않으면 가중치가 더 높은 [2, 2, 2]를 먼저 방문하고 다음으로 [1]을 방문하게 될 텐데, 이는 가중치를 최소로 하는 경로를 반환하는 것을 보장해주지 않는다.

따라서 0-1 BFS 알고리즘의 핵심은 가중치가 더 낮은 간선이라면 큐의 앞에 삽입하여 가중치를 최소로 하는 경로를 반환하도록 만드는 것이다.

 

 

그럼 다시 문제로 돌아와서, 0-1 bfs 알고리즘을 문제에 적용해보자.

문제에서 갈 수 있는 곳은 [죽음의 구역, 위험한 구역, 안전한 구역]이 있다.

이때 우리가 구해야 하는 것은 잃는 생명의 최솟값이며, 위험한 구역은 가중치가 1, 안전한 구역은 가중치가 0이다. (죽음의 구역은 아예 갈 수 없도록 설정한다.)

 

그렇다면 더 작은 가중치가 항상 큐의 앞에 오게하기 위해서 안전한 구역을 만날 때는 queue의 unshift 연산을 사용하면 된다.

다른 언어의 경우 deque을 사용하는 것 같았으나, javascript는 제공되지 않아 queue의 연산들을 직접 구현해주었다.

 

 

코드

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

const N = +input[0];
const danger = input.slice(1, N + 1).map((x) => x.split(" ").map(Number));

const M = +input[N + 1];
const kill = input.slice(N + 2).map((x) => x.split(" ").map(Number));

const map = Array.from({ length: 501 }, () => Array(501).fill(0));
const visited = Array.from({ length: 501 }, () => Array(501).fill(-1));

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

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

  push(data) {
    const newNode = new Node(data);

    if (this.size === 0) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }

    this.tail = newNode;
    this.size++;
  }

  shift() {
    const data = this.head.data;

    this.head = this.head.next;
    this.size--;

    if (this.size === 0) {
      this.head = null;
      this.tail = null;
    }

    return data;
  }

  unshift(data) {
    const newNode = new Node(data);

    if (this.size === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }

    this.size++;
  }

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

for (let [x1, y1, x2, y2] of danger) {
  let sr = x1 > x2 ? x2 : x1;
  let br = x1 > x2 ? x1 : x2;
  let sc = y1 > y2 ? y2 : y1;
  let bc = y1 > y2 ? y1 : y2;

  for (let i = sr; i <= br; i++) {
    for (let j = sc; j <= bc; j++) {
      map[i][j] = 1;
    }
  }
}

for (let [x1, y1, x2, y2] of kill) {
  let sr = x1 > x2 ? x2 : x1;
  let br = x1 > x2 ? x1 : x2;
  let sc = y1 > y2 ? y2 : y1;
  let bc = y1 > y2 ? y1 : y2;

  for (let i = sr; i <= br; i++) {
    for (let j = sc; j <= bc; j++) {
      map[i][j] = 2;
    }
  }
}

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

const bfs = () => {
  const queue = new Queue();
  queue.push([0, 0, 0]);

  visited[0][0] = 0;

  while (!queue.isEmpty()) {
    const [cx, cy, lessCnt] = queue.shift();

    if (cx === 500 && cy === 500) {
      return lessCnt;
    }

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

      if (nx < 0 || nx > 500 || ny < 0 || ny > 500) continue;
      if (visited[nx][ny] > -1 || map[nx][ny] === 2) continue;

      visited[nx][ny] = 0;

      if (map[nx][ny] === 1) queue.push([nx, ny, lessCnt + 1]);
      else queue.unshift([nx, ny, lessCnt]);
    }
  }

  return -1;
};

console.log(bfs());

후기

문제를 읽고 가중치가 있는 그래프 문제라는 것을 알아차리지 못했다.

이동하는 와중에 비용이 다르다면 가중치가 다른 문제임을 인지하자.

또한 이 문제를 단순 bfs로 풀면 안되는 이유는 최단 경로가 최적해라고 보장할 수 없기 때문이다.

 

참고

https://algorithmstudy-mju.tistory.com/212

BOJ - 1584 ) 게임