[백준] 상근이의 여행(9372)-JavaScript

문제

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

문제 파악

• 모든 국가를 돌기 위해 타야하는 가장 적은 수의 비행기 종류를 구하는 문제이다.
• 최장, 최단은 BFS의 전형적인 문제 유형이다.

문제 풀이

• 이전 문제에서 BFS 문제를 풀지 못하여, 해당 유형으로 풀고자 했다.
• 상근이의 출발 국가는 어디일까...🤔 어차피 모든 배열을 돌기 때문에, 시작 노드를 임의로 1로 주었다. (코드에서는 0)
• 노드와 변수(visited)의 인덱스를 맞추기 위해 노드 -1을 하였다.
  노드를 방문했는지만 알면되기 때문에, visited 변수의 모든 index가 true가 되면 탐색을 멈추기 위해서이다.
• count는 노드 방문 횟수 -1이며, 간선의 수를 의미한다. (상근이가 타야하는 비행기의 종류)

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

let number = Number(input[0]);
let result = [];
let idx = 1;

for (let i = 0; i < number; i++) {
    let arr = [];
    let [nodeNum, edgeNum] = input[idx++].split(" ").map(Number);
    for (let j = 0; j < edgeNum; j++) {
        arr[j] = input[idx++].split(" ").map(Number);
    }

    const visited = new Array(nodeNum).fill(false);
    visited[0] = true;
    const queue = [0];
    let count = 0;

    while (queue.length) {
        const head = queue.shift();
        for (let node of arr) {
            if (node[0] - 1 === head && !visited[node[1] - 1]) {
                queue.push(node[1] - 1);
                visited[node[1] - 1] = true;
                count++;
            } else if (node[1] - 1 === head && !visited[node[0] - 1]) {
                queue.push(node[0] - 1);
                visited[node[0] - 1] = true;
                count++;
            }
        }
        if (!visited.includes(false)) break;
    }
    result[i] = count;
}

console.log(result.join('\n'));