백준 11403 경로 찾기 (node.js)

문제

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

 

 

문제 해석

이 문제는 그래프 이론과 비슷한 방법으로 풀면 된다.

다만, 정점 i에서 j로 가는 간선임으로 graph 추가 시 양 방향 추가가 아닌 단 방향으로 추가해 주면 된다.

 

풀이

const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

function solution(input) {
  const [N, M] = input.shift().split(" ").map(Number);
  const lines = input.map((v) => v.split(" ").map(Number));
  const visited = Array(N + 1).fill(false);
  const graph = Array.from(Array(N + 1)).map(() => []);
  let answer = 0;
  const checkArr = [];

  lines.map(([from, to]) => {
    graph[from].push(to);
    graph[to].push(from);
  });

  const bfs = (start) => {
    let queue = [start];
    while (queue.length) {
      const node = queue.shift();
      for (const vertax of graph[node]) {
        if (!visited[vertax]) {
          visited[vertax] = true;
          queue.push(vertax);
        }
      }
    }
  };

  for (let i = 1; i <= N; i++) {
    if (visited[i]) continue;
    bfs(i);
    answer++;
  }

  return answer;
}

console.log(solution(input));

 

 

끝