[구름톤 챌린지] 대체 경로 (JS)

풀이 과정

1. 도시 번호를 키로, 연결된 도시 배열을 값으로 가지는 객체 생성
2. visited 배열 생성하고 Infinity로 초기화
3. N일만큼 반복
   이때 i가 출발 또는 도착 도시와 같으면 -1 출력 후 넘기기
4. 현재 도시에서 이동 가능한 도시들을 BFS 탐색
   현재 도시가 공사중이면 넘기기
   visited 배열에 최소 이동 거리를 갱신
   현재 도시가 도착 도시면 반복문 빠져나가기
5. 이동 횟수가 갱신되었으면 갱신된 값, 아니면 -1 출력

코드

const readline = require('readline');
let rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = [];
let N, M, S, E;
rl.on('line', (line) => {
  input.push(line.split(' ').map(Number));
  [N, M, S, E] = input[0];
  if (input.length === M + 1) {
    rl.close();
  }
});

rl.on('close', () => {
  const obj = {};
  for (let i = 1; i <= M; ++i) {
    const [u, v] = input[i];
    if (!obj[u]) obj[u] = [];
    if (!obj[v]) obj[v] = [];
    obj[u].push(v);
    obj[v].push(u);
  }

  for (let i = 1; i <= N; ++i) {
    if ([S, E].includes(i)) {
      console.log(-1);
      continue;
    }
    const visited = Array(N + 1).fill(Infinity);
    const q = [S];
    visited[S] = 1;
    while (q.length) {
      const curr = q.shift();
      if (!obj[curr]) continue;
      for (const next of obj[curr]) {
        if (next === i) continue;
        if (visited[next] <= visited[curr] + 1) continue;
        visited[next] = visited[curr] + 1;
        if (next === E) break;
        q.push(next);
      }
    }
    console.log(visited[E] === Infinity ? -1 : visited[E]);
  }
});

🤔

앞서 풀었던 문제랑 비슷한가 싶다가도 아니고... 어떻게 기우다가 테스트 케이스를 일부만 통과하게 됐다. 1시간 넘게 고민했으니 나머지는 내일...

09/08 해설 참조 후 추가
visited에 최소 이동 횟수를 갱신해나갈 생각은 전혀 못했다. 문제 정답률이 너무 높아서 약간 자괴감이 들긴 하는데... 아직 내 갈길이 멀긴 하다.