[백준] 2606 바이러스 Node.js

바이러스

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

---

01 […new Array(N)] 설명

[…new Array(N)] 과 [new Array(N)]의 차이점

1. [new Array(N)]: 모든 요소를 undefined로 초기화된 크기 N의 배열 생성

   const num = 3;
   const newArr = [...new Array(num)]; 
   console.log(newArr);  //[Array(3)]

2. let Arr = […new Array(N)] : …rest parameter가 있는 경우 array로 초기화된 배열 생성

   const num2 = 3;
   const arr = [new Array(num2)];
   console.log(arr); //// [arr(), undefined, undefined]
   console.log(arr[0]) // […]

　 　

02 배열 생성

greph를 생성한 후 각각의 요소들에 인접 노드들을 push해주어야 하기 때문에 배열 안에 배열을 넣어준다

let graph = [...new Array(num+1)].map(()=>[]); //[Array(0), Array(0), Array(0), Array(0), Array(0), Array(0), Array(0), Array(0)]
let visited = Array(num +1).fill(false); //(8) [false, false, false, false, false, false, false, false]

cf. rest parameter가 없는 경우

let graph = [new Array(num+1)].map(()=>[]); 
console.log(graph); // (1) [Array(0)]
console.log(graph.length); // 1

　 　

03 graph 에 인접 노드 push

for문으로graph안에 방문한 노드를 표시해준다

1번 노드의 방문은 index 1에 , 2번 노드의 방문은 index2에 push로 연결해준다.
예를들어 주어진 input에 1과 3이 연결되어 있는 경우 [1 : 3] , [3 : 1]

이렇게 양 쪽 노드에 다 push 되어있어야 한다.

for (let i=0; i<link; i++){
    let [from,to] = input[i].split(' ').map(Number);//짝 생성(FROM,TO) 
    graph[from].push(to);
    graph[to].push(from);
}

　 　 　

04 dfs함수 작성

dfs함수 안의 visited\[from\] = true; 는 for문 밖으로 빼주어 한 번만 적용되게 한다
: 처음 시작점인 from에 대한 방문 표시

function dfs(from){
        visited[from] = true;
    for (let to of graph[from]){
        if (!visited[to]){
            visited[to] =1;
            answer ++;
            dfs(to);
        }
    }
}

　 　

전체 코드

const fs = require('fs');
let [num,link,...input] = fs.readFileSync('dev/stdin').toString().trim().split(/\n/);

num = Number(num);
link = Number(link);
//console.log(typeof(num),link,arr);

let graph = [...new Array(num+1)].map(()=>[]); //노드 번호 1부터 시작
let visited = [...new Array(num + 1)].fill(false);
let answer =0;


    // console.log(input) //무방향 그래프 생성 
for (let i=0; i<link; i++){
    let [from,to] = input[i].split(' ').map(Number);//짝 생성(FROM,TO) 
    graph[from].push(to);
    graph[to].push(from);

}

function dfs(from){
        visited[from] = true;
    for (let to of graph[from]){
        if (!visited[to]){
            visited[to] =1;
            answer ++;
            dfs(to);
        }
    }
}
dfs(1);
console.log(answer);