[백준/node.js] 11724번 연결 요소의 개수

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

11724번: 연결 요소의 개수

 

• 사용언어 : node.js
• 알고리즘 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
• Solved.ac Tier : Silver II

 

 

node.js 코드

1. 문제 정리

방향이 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 프로그램을 작성하란다. 

그림과 같이 노드의 개수는 10개지만 연결 되어있는 노드들의 개수는 총 4개이다. 이런 걸 연결 요소의 개수라고 한다. 

정점의 개수와 간선의 개수를 제일 첫 줄에서 받고 둘째줄 부터 간선의 양 끝점 u와 v 즉 시작점과 끝점을 준다고 한다. 

다음과 같은 문제에선 그래프 노드들을 배열로 연결 해준 다음 DFS또는 BFS의 횟수를 계산 해 준다면 연결 요소의 개수를 자연스럽게 알 수 있다.

 

2. 완성 코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : '../ans.txt';
let [input, ...inputs] = require('fs').readFileSync(filePath).toString().trim().split("\n");
let [n, m] = input.split(" ").map((e)=>+e), graph = [], visited=new Array(n+1).fill(false)
let cnt = 0
for(let i = 1; i <= n; i++) graph[i] = []
for(let i = 0; i <inputs.length; i++){
    let [a, b] = inputs[i].split(" ").map((e)=>+e)
    graph[a].push(b)
    graph[b].push(a)
}   

for(let i = 1; i <= n; i++){
    if(!visited[i]){
        DFS(i);
        cnt++;
    }
}

console.log(cnt)

function DFS(v){
    if(visited[v] == true)  return
    visited[v] = true
    for(let i = 0 ; i < graph[v].length; i++){
        if(visited[graph[v][i]] == false){
            DFS(graph[v][i])
        }
    }
}

제출 현황

질문또는 코드 리뷰는 댓글로 부탁드립니다!