[백준] node.js/ 2606_바이러스

이번 문제는 쉽지 않았다.

dfs를 이용해 풀이하는 문제였고, 나는 dfs에 아직 약하기 때문에 더 많이 공부해야 한다ㅏ.

 

 

 

정답 풀이

n+1을 하는 이유는 인덱스와 수를 맞춰주기 위해서! ( 0 idx의 값은 쓰지 않는다고 보면 된다.)

const fs = require('fs');

let input = (fs.readFileSync('./dev/stdin') + '').toString().trim().split('\n');
let n = Number(input.shift());
let m = Number(input.shift());

let graph = [...new Array(n + 1)].map(() => []);
let visited = new Array(n + 1).fill(false);
let ans = 0;

visited[1] = true;

const dfs = (start) => {
  graph[start].map((dest) => {
    if (!visited[dest]) {
      visited[dest] = true;
      ans += 1;
      dfs(dest);
    }
  });
};


input.map((i) => {
  const [start, dest] = i.split(' ').map((ele) => Number(ele));
  graph[start].push(dest);
  graph[dest].push(start);
});

dfs(1);

console.log(ans);

1) 연결관계를 표현할 graph 생성

2) 방문 여부를 표현할 visited 배열생성

3) dfs 생성 : dfs는

- 그래프 배열을 돌면서 해당 graph를 방문했는지 확인한 후

- 방문하지 않았다면 그 숫자의 graph를 다시 방문 

4) dfs로 graph를 돌며 들어왔던 곳 나갔던 곳을 둘다 방문해봄!

 

 

 

input map에서 console을찍어보면 이렇게 graph가 채워지게 된다.

 

한가지 예시를 설명해보자면 위의 그림과 같이 graph가 다 채워진 후에 dfs가 시작되게 되는데,

 

dfs 호출	graph	visited
dfs(1)	[2,5]	[   false, true,   false, false,   false, false,   false, false ]
dfs(2)	[1,3,5] 1은 방문함 [1,3,5]	[   false, true,   true, false,   false, false,   false, false ]
dfs(3)	[2] 2는 방문함 다시 위의 dfs(2)로 재귀	[   false, true,   true, true,   false, false,   false, false ]
dfs(5)	[1,3,5] 1은 방문함 [1,3,5] [1,3,5]	[   false, true,   true, true,   false, true,   false, false ]

...

 

 

이런 식으로 dfs를 부르고 다시 재귀하고 하는 과정을 반복해 연결된 그래프를 탐색한 후 바이러스에 걸린 개수를 확인할 수 있다.

 

 

 

이 과정에서 나는 처음에 큰 실수를 해서 삽질을 오래 했다.

graph를 생성할 당시 나는 아무 생각 없이 graph2와 같이 만들었는데, 

let graph = [...new Array(n + 1)].map(() => []);
// [ [],[],[] ]

let graph2 = new Array(n + 1).fill([]);
// [ [],[],[] ]

바로 graph2와 같이 생성하게 되면 graph2의 모든 element( 즉 배열[])들이 그 값을 공유하게 되서

graph가 계속 같은 값을 가지게 된다..

따라서 graph와 같이 값을 따로 만든후에 map으로 변경해야 한다.

[...new Array(n)] 
// [ undefined, undefined, undefined ]

[...new Array(n)].map((ele)=>[]))
// [ [],[],[] ]

// graph

[
  [], [ 2 ], [ 1 ],
  [], [],    [],
  [], []
]


// graph2
[
  [ 2, 1 ], [ 2, 1 ],
  [ 2, 1 ], [ 2, 1 ],
  [ 2, 1 ], [ 2, 1 ],
  [ 2, 1 ], [ 2, 1 ]
]