[백준11724_자바스크립트(javascript)] - 연결 요소의 개수

🔴 문제

연결 요소의 개수

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const [n, m] = inputs.shift();
const map = Array.from({ length: n + 1 }, () => []);
const visited = Array.from({ length: n + 1 }, () => false);

for (const input of inputs) {
  const [u, v] = input;

  map[u].push(v);
  map[v].push(u);
}

const dfs = (node) => {
  visited[node] = true;

  for (let i = 0; i < map[node].length; i++) {
    if (!visited[map[node][i]]) dfs(map[node][i]);
  }
};

let ans = 0;
for (let i = 1; i <= n; i++) {
  if (!visited[i]) {
    dfs(i);
    ans += 1;
  }
}

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

방향 없는 그래프의 연결 개수를 확인해 줘야 하므로 dfs를 떠올렸다.
먼저 입력되는 그래프 정보는 양방향 그래프이므로 인접 리스트 형태로 저장해준다.
1부터 n까지 노드의 개수만큼 반복하며 방문하지 않은 노드일 경우 dfs를 수행해준다.
dfs를 수행하면서 방문처리를 해준 뒤 해당 노드랑 연결된 노드가 방문하지 않은 노드라면, 재귀호출을 해주면 된다.
한 번의 dfs를 수행하면 연결 요소가 하나 만들어진 것이기 때문에 ans값을 1증가시켜준다.

🔵 Ref