백준 5214번 환승 JavaScript 풀이 [BFS]

백준 5214번 환승 문제를 자바스크립트로 BFS 알고리즘을 이용해서 풀어보았다. 

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

 

1) 처음 작성한 코드 -> 메모리 초과로 실패

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

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const element = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return element;
  }
  getLength() {
    return this.tail - this.head;
  }
}

// n : 역의 수, k : 하이퍼튜브당 연결 역의 수, m : 하이퍼튜브 개수
let [n, k, m] = input[0].split(' ').map(Number);
let graph = new Array(n+1).fill().map(_ => []);
for (let t=1; t<=m; t++) {
  let stations = input[t].split(' ').map(Number);
  for (let i=0; i<stations.length; i++) {
    for (let j=0; j<stations.length; j++) {
      if (i !== j) graph[stations[i]].push(stations[j])
    }
  }
}

// 방문 배열
let visited = new Array(n+1).fill(0);
visited[1] = 0;
queue = new Queue();
queue.enqueue(1);

// BFS 진행
while (queue.getLength() != 0) {
  let x = queue.dequeue();

  for (next of graph[x]) {
    if (visited[next] == 0) {
      visited[next] = visited[x] + 1;
      queue.enqueue(next)
    }
  }
}

console.log(visited[n] + 1)

 

2) Map 객체로 시도 -> 또 메모리 초과로 실패

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

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const element = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return element;
  }
  getLength() {
    return this.tail - this.head;
  }
}

// n : 역의 수, k : 하이퍼튜브당 연결 역의 수, m : 하이퍼튜브 개수
let [n, k, m] = input[0].split(' ').map(Number);
let graph = new Array(n+1).fill().map(_ => []);
for (let t=1; t<=m; t++) {
  let stations = input[t].split(' ').map(Number);
  for (let i=0; i<stations.length; i++) {
    for (let j=0; j<stations.length; j++) {
      if (i !== j) graph[stations[i]].push(stations[j])
    }
  }
}

// 방문 배열
let visited = new Map();
visited.set(1, 0);
queue = new Queue();
queue.enqueue(1);

// BFS 진행
while (queue.getLength() != 0) {
  let x = queue.dequeue();

  for (next of graph[x]) {
    if (!visited.has(next)) {
      visited.set(next, visited.get(x) + 1)
      queue.enqueue(next)
    }
  }
}

console.log(visited.get(n) + 1)
console.log(visited)
console.log(graph)

 

3) 하이퍼튜브 사용 -> 성공!

while문 쪽이 문제가 아니라, 처음에 graph에 넣을때부터 문제였다.

하이퍼튜브를 사용하지 않고 노드로만 하니까 while문에서 큐에 들어가는 노드가 너무 많아져서 메모리 초과가 난 것이었다.

그래서 graph는 노드와 하이퍼튜브와의 연결 관계를 넣어주고, 하이퍼튜브 배열을 따로 만들어서 각 하이퍼튜브마다 연결된 노드 번호들을 넣어준 후에 작성했다.

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

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const element = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return element;
  }
  getLength() {
    return this.tail - this.head;
  }
}

// n : 역의 수, k : 하이퍼튜브당 연결 역의 수, m : 하이퍼튜브 개수
let [n, k, m] = input[0].split(' ').map(Number);

// 하이퍼튜브 정보(N개의 역과 M개의 하이퍼튜브는 모두 노드)
let hyperTube = new Array(m+1);
// 노드와 하이퍼튜브간의 연결 정보
let graph = new Array(n+1).fill().map(_ => []);

for (let t=1; t<=m; t++) {
  let arr = input[t].split(' ').map(Number);
  hyperTube[t] = arr;
  
  for (let node of arr) {
    graph[node].push(t)
  }
};


// 결과
let result = -1;

// 방문 배열
let visitedNode = new Array(n+1).fill(0);
let visitedHyper = new Array(m+1).fill(0);
visitedNode[1] = 1;
queue = new Queue();
queue.enqueue(1);

// BFS 진행
while (queue.getLength() != 0) {
  let x = queue.dequeue();

  // node -> hyper
  for (hyper of graph[x]) {
    if (visitedHyper[hyper] == 0) {
      visitedHyper[hyper] = visitedNode[x] + 1;

      // hyper -> node
      for (next of hyperTube[hyper]) {
        if (visitedNode[next] == 0) {
          visitedNode[next] = visitedHyper[hyper] + 1
          queue.enqueue(next)
        }
      }
    }
  }
}

if (visitedNode[n] == 0) console.log(-1)
else console.log((visitedNode[n] + 1) / 2)

 

기억을 위해 예시를 남겨보자면

테스트 케이스 1번과 같은 경우

하이퍼튜브를 안 쓰고 노드로만 그래프를 만들어서 하게 되면 인접 리스트는 다음과 같이 나올 것이다.

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

 

이대로 큐에 넣는다면, 

1) 
1번 출발

2) 
1->[2, 3, 4, 5]

3) 
2->[1, 3] + 3->[1, 2, 6, 7] + 4->[1, 5] + 5->[1, 4, 6, 7]
이 중에 하나씩만 방문처리 됨 -> 개수로 큰 차이 없음

4) 
3->[1, 2, 6, 7] + 2->[1, 3] + 6->[3, 5, 7, 8, 9] 
9를 만났으므로 종료되어서 답이 4
(+ 7->[3, 5, 6] + 5->[1, 4, 6, 7] + 4->[1, 5] + 6->[3, 5, 7, 8, 9] + 7->[3, 5, 6])

 

이렇게 점차 큐에 들어가야 할 노드들어 엄청 불어날 것이다.

이때 하이퍼튜브를 사용한다면

// graph 변수 (H는 하이퍼튜브 번호를 의미)
1 | 1H, 2H
2 | 1H
3 | 1H, 3H
4 | 2H
5 | 2H, 4H
6 | 3H, 5H
7 | 3H, 4H
8 | 5H
9 | 5H

// hyperTube 변수
1 | 1, 2, 3
2 | 1, 4, 5
3 | 3, 6, 7
4 | 5, 6, 7
5 | 6, 8, 9

 

이대로 BFS를 진행한다면

1) 
1번 출발

2)
1->[1H, 2H]
1H->[1, 2, 3]
2H->[1, 4, 5]

3)
2->[1H]->[1, 2, 3]
3->[1H, 3H]->[1, 2, 3]+[3, 6, 7]
4->[2H]->[1, 4, 5]
5->[2H, 4H]->[1, 4, 5]+[5, 6, 7]
하이퍼튜브 중 방문 안한 것만 찾음
1H라면
3->[3H]->[3, 6, 7]
4->[2H]->[1, 4, 5]
5->[4H]->[5, 6, 7]
이렇게만 남음

4)
3->[1H, 3H]
6->[3H, 5H]->[3, 6, 7]+[6, 8, 9]
9를 만나서 종료됨

 

방문처리에서 하이퍼튜브 번호 자체가 걸러지다보니 큐에 들어갈 번호가 확 줄게된다.