[백준]5214번 '환승' 문제 풀이 - JavaScript

[백준]5214번 '환승' 문제 풀이 - JavaScript

난이도: 골드 2

풀이 알고리즘: BFS

문제

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

입력

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

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

출력

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

예제 입력 1 

9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

 

1-3-6-9나 1-5-6-9로 이동하면 된다.

예제 출력 1 

4

반응형

👉 풀이 코드

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

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }

  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }

  peek() {
    return this.items[this.headIndex];
  }

  size() {
    return this.tailIndex - this.headIndex;
  }
}

const [n, k, m] = input[0].split(' ').map(Number);
const graph = Array.from({ length: n + m + 1 }, () => []);
for (let i = 1; i <= m; i++) {
  const arr = input[i].split(' ').map(Number);
  for (const x of arr) {
    graph[x].push(n + i);
    graph[n + i].push(x);
  }
}
const visited = new Set([1]);
const queue = new Queue();
queue.enqueue([1, 1]);

while (queue.size() !== 0) {
  const [dist, now] = queue.dequeue();

  if (now === n) {
    console.log(Math.floor(dist / 2) + 1);
    return;
  }

  for (const y of graph[now]) {
    if (!visited.has(y)) {
      visited.add(y);
      queue.enqueue([dist + 1, y]);
    }
  }
}

console.log(-1);

💡풀이 해설

일종의 최단 거리 문제이며, 간선의 비용이 동일하기 때문에 BFS로 최단 거리를 계산할 수 있다.

 

문제 해결의 핵심 팁은 하이퍼튜브를 포함하여 전체 노드를 그래프로 구성해야 한다.

 

예제 1번을 예시로 들면,

1 -> H -> 3 -> H -> 6 -> H -> 9
위 과정을 통해 1번 역부터 N번 역까지 도착할 수 있게 된다.

하이퍼튜브는 중간 다리 역할을 해준다고 생각하면 된다.

 

마지막에 계산할 때는 역 이동 거리만 계산하면 되기때문에 하이퍼 튜브 이동이 포함된 비용을 빼고 1번 역도 비용에 포함시키기 위해서 이동거리 / 2 + 1을 해준다.

 

graph에 인접 리스트를 생성할 때, 각 역이 존재하는 하이퍼 튜브와 하이퍼튜브가 갖고 있는 역의 번호를 graph에 넣어준다.

 

1번 예제를 예시로 인접 리스트를 생성하면 아래와 같은 결과가 생성된다.

[
  [],             [ 10, 11 ],
  [ 10 ],         [ 10, 12 ],
  [ 11 ],         [ 11, 13 ],
  [ 12, 13, 14 ], [ 12, 13 ],
  [ 14 ],         [ 14 ],
  [ 1, 2, 3 ],    [ 1, 4, 5 ],
  [ 3, 6, 7 ],    [ 5, 6, 7 ],
  [ 6, 8, 9 ]
]

총배열의 길이는 n(역의 개수) + m(하이퍼 튜브의 개수) + 1 이 된다.

계산하기 쉽게 0번 인덱스는 사용하지 않고 1번 역부터 시작하기 때문에 1번 인덱스부터 시작한다.

1번 ~ N번까지는 역이 어떤 하이퍼 튜브에 포함되어 있는지.
N + 1번 부터 M번 까지는 몇 번째 하이퍼 튜브가 어떤 역들을 포함하고 있는지 정보를 갖고 있다.

 

1번 인덱스부터 예를 들자면 1번 인덱스(역)는 10번 인덱스(하이퍼튜브)와 11번 하이퍼튜브에 존재한다는 뜻이고 10번 인덱스(하이퍼튜브)는 1,2,3번 역을 포함하고 있다는 것이다.

 

그래서 큐에는 [거리, 노드]가 들어가게 되고 1번 노드부터 순차적으로 너비우선탐색을 진행한다.

방문을 하면서 해당 노드의 모든 요소들을 큐에 넣어주기 때문에 방문 처리를 해주면서 방문하지 않는 노드에 대해서만 방문을 진행해야 한다.

 

진행하다가 현재 노드가 n번이 됐다면 결과를 출력한다.

 

큐가 빌 때까지 N번에 도달하지 못했다면 -1을 출력한다.