[코딩테스트] 백준 - 5214번 환승 BFS (JS)

문제설명

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

제한사항

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다.

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

문제풀이

1번에서 N번 노드까지의 최단 경로를 구하는 문제다.

처음에는 Set을 사용해 각 하이퍼튜브에 있는 노드를 연결된 노드에 저장해 주는 방식을 사용해 BFS를 수행해서 문제를 풀었는데 메모리 초과가 발생했다.

두 번째로, 하이퍼튜브 인덱스를 하이퍼튜브와 연결된 각 노드에 push 하는 방법으로 문제를 풀었는데, 또 메모리 초과가 발생했다.

세 번째로, 하이퍼튜브에 대한 방문기록을 담은 배열을 만들어 해당 하이퍼튜브를 방문한 적 있으면 해당 하이퍼튜브는 건너뛰도록 구현을 했더니 성공했다.

따라서 이 문제를 풀기 위해서는 하이퍼튜브와 연결된 노드에 하이퍼튜브 인덱스를 추가한 후 해당 노드에 담긴 하이퍼튜브들을 하나씩 꺼내고, 해당 하이퍼튜브와 연결된 노드에 방문하면 된다.

노드와 연결된 모든 하이퍼튜브를 방문하면 메모리 초과가 발생하기 때문에 방문한 적 있는 하이퍼튜브에 대해서는 나중에 방문하지 않도록 처리해줘야 한다.

하이퍼튜브와 연결된 노드에 방문할 때는 현재 거리 + 1한 값과 연결된 노드의 최단 거리를 비교해 더 작으면 현재 거리 + 1한 값으로 업데이트 해주면 된다.

코드

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

class Queue {
    constructor() {
      this.queue = [];
      this.head = 0;
      this.tail = 0;
    }
  
    size() {
      return this.tail - this.head;
    }
  
    shift() {
      const item = this.queue[this.head];
      delete this.queue[this.head++];
      return item;
    }
  
    push(item) {
      this.queue[this.tail++] = item;
    }
  }

let queue = new Queue();

const [N,K,M] = input[0].split(' ').map(Number);
const hyperLinks = input.slice(1, 1 + M).map(s=> s.split(' ').map(Number));

let visited = new Array(M).fill(false);
let graph = Array.from(new Array(N + 1), s => s = []);
for(let i = 0; i < hyperLinks.length; i++) {
  for(let node of hyperLinks[i]) {
    graph[node].push(i); 
  }
}

let costArray = new Array(N + 1).fill(Infinity);
queue.push([1, 1]);
costArray[1] = 1;
bfs()
console.log(costArray[N] === Infinity ? -1 : costArray[N]);

function bfs() {
  while(queue.size() !== 0) {
    const [curNode, curCost] = queue.shift();

    for(let hyper of graph[curNode]) {
      if(visited[hyper]) continue;
      visited[hyper] = true;
      for(let nextNode of hyperLinks[hyper]) {
        if(costArray[nextNode] >= curCost + 1) {
          costArray[nextNode] = curCost + 1;
          queue.push([nextNode, curCost + 1]);
        }
      }
    }

  }
}