구름톤 챌린지 19일차 대체경로 [Javascript]

문제

플레이어는 1번부터 N번까지의 번호가 붙은 N개의 도시와 M개의 도로가 있는 나라에 살고 있다. 각 도로는 서로 다른 두 도시를 양방향으로 연결하고 있고, 주어진 도로만을 이용해 임의의 두 도시 사이를 이동하는 것이 가능하다.

플레이어는 차를 타고 S번 도시에서 E번 도시로 이동하려고 한다. 플레이어가 두 도시 사이를 이동할 때는 항상 가장 작은 수의 도시를 거치는 경로를 따라 이동한다.

 

플레이어가 사는 나라에서는 자주 공사를 한다 i일 뒤에는 i번 도시에서 하루동안 공사를 할 예정이다. 어떤 도시에서 공사를 하고 있으면 그 도시에 연결된 모든 도로를 일시적으로 사용할 수 없다.

앞으로 N일 동안 매일 플레이어는 S번 도시에서 E번 도시로 이동한다고 할 때, 각 날마다 플레이어가 이동하는 경로에 포함되는 도시의 수를 구해서 출력해보자. 단 출발도시와 도착 도시에서 공사하거나 두 도시 사이를 이동할 수 없는 경우에는 -1을 대신 출력한다.

 

const readline = require('readline');
let rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = [];
rl.on('line', (line) => {
  input.push(line);
});

rl.on('close', () => {
  const [n, m, s, e] = input[0].split(' ').map((v) => parseInt(v));

  const graph = new Array(n).fill(null).map(() => []);

  for (let i = 0; i < m; ++i) {
    const [u, v] = input[i + 1].split(' ').map((v) => parseInt(v));

    graph[u - 1].push(v - 1);
    graph[v - 1].push(u - 1);
  }

  function bfs(s, e, blocked) {
    const visited = new Array(n).fill(false);

    const queue = [];

    queue.push(s);
    visited[s] = 1;

    if (s === blocked) {
      return -1;
    }

    while (queue.length) {
      const currentCity = queue.shift();

      if (currentCity === e) {
        return visited[currentCity];
      }

      for (const neighbor of graph[currentCity]) {
        if (!visited[neighbor] && !(blocked === neighbor)) {
          visited[neighbor] = visited[currentCity] + 1;
          queue.push(neighbor);
        }
      }
    }

    return -1;
  }

  for (let i = 0; i < n; ++i) {
    const blocked = i;

    let start = s - 1;
    const end = e - 1;

    const path = bfs(start, end, blocked);
    console.log(path);
  }
});