백준 2606 자바스크립트

문제

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

2606번: 바이러스

접근 

기본적인 그래프 탐색 문제. 

연결된 노드가 몇 개인지를 구하는.

 

단, 맨 처음 노드 시작을 인덱스 0이 아닌 1로 시작해줘야 한다.

풀이

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

function solution(input) {
  const N = +input.shift(); // 노드 수
  const M = +input.shift(); // 간선 수
  const edges = input.map((v) => v.split(" ").map(Number));

  // 그래프 그리기
  const vertices = Array(N + 1)
    .fill(0)
    .map(() => []);
  for (let edge of edges) {
    const [v0, v1] = edge;
    vertices[v0].push(v1);
    vertices[v1].push(v0);
  }

  // 실행
  const seen = new Set();
  let count = 0;
  const dfs = (start) => {
    for (let end of vertices[start]) {
      if (!seen.has(end)) {
        seen.add(end);
        count++;
        dfs(end);
      }
    }
  };
  seen.add(1);
  dfs(1);
  console.log(seen);
  return count;
}

console.log(solution(input));

참조: https://www.acmicpc.net/source/54379165

로그인