[백준18352_자바스크립트(javascript)] - 특정 거리의 도시 찾기

🔴 문제

특정 거리의 도시 찾기

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const [n, m, k, x] = inputs.shift();
const map = Array.from({ length: n + 1 }, () => []);

for (const input of inputs) {
  const [a, b] = input;
  map[a].push(b);
}

const visited = Array.from({ length: n + 1 }, () => false);

const q = [x];
visited[x] = 0;

while (q.length) {
  const node = q.shift();

  for (let i = 0; i < map[node].length; i++) {
    if (visited[map[node][i]] === false) {
      visited[map[node][i]] = visited[node] + 1;
      q.push(map[node][i]);
    }
  }
}

const ans = [];
for (let i = 1; i <= n; i++) {
  if (visited[i] === k) ans.push(i);
}

console.log(ans.length ? ans.sort((a, b) => a - b).join('\n') : -1);

🟢 풀이

⏰ 소요한 시간 : -

최단거리를 찾아야 하기 때문에 bfs로 풀이했다.
그래프 정보를 저장할 배열 map을 인접리스트 형태로 만들어준다.
이 때 단방향 연결임을 주의한다.
그 후 방문배열을 만들고 출발할 도시 번호 k를 큐에 넣어준다. 출발한 도시 번호는 방문 처리를 위해 0으로 값을 둔다.
그 후 큐를 순회하면서 bfs를 수행할 텐데, 현재 노드랑 연결된 노드의 개수만큼 반복을 하며 현재 노드와 연결된 노드를 미방문상태일 때만 방문해준다.
방문처리는 이전노드 + 1 을 해주고, 큐에 넣어준다.

이러면 시작노드로부터 각 노드까지 걸리는 최단 거리가 visited배열에 기록되어 있을 텐데 최단거리가 k인 도시만 ans 배열에 넣어준다.
마지막으로 ans의 길이가 0보다 클 때만 정려된 값을 출력하고 아니면 -1을 출력한다.

🔵 Ref