백준 11724:연결 요소의 개수 - javascript(dfs)

문제 출처 

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

11724번: 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

문제 풀이 힌트 

dfs을 이용해서 풀자 !

예) 첫번째 예시

1. 연결된 노드들을 그래프로 나타내자. 

 graph[1] = [2,5]; // 정점 1과 연결되어 있는 정점은 2와 5다. 

 graph[2] = [1,5]; 

 graph[3] = [4]; 

 graph[4] = [3,6]; 

 graph[5] = [1,2]; 

 graph[6] = [3,4]; 

2. 반복문을 활용해서 그래프를 차례대로  방문한다.

-  graph[1] => graph[2] => graph[3] => graph[4] ...

3. dfs를 활용해서 방문한 graph[i]의 요소들을 하나씩 다 방문한다. 

- 방문한 graph[1]의 요소들을 하나씩 방문한다. => 정점 2와 5를 방문! 

 

정답 풀이 코드 

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
let [n, m] = input[0].split(" ").map(Number);
let graph = []; 
for(let i=1; i<=n; i++){
    graph[i] = []; 
} 
for(let i=0; i<m; i++){
    let [from, to] = input[i+1].split(" ").map(Number); 
    graph[from].push(to); 
    graph[to].push(from); 
}
let visited = new Array(n+1).fill(false); 

function dfs(start){
    visited[start] = true; 
   for(let i=0; i<graph[start].length; i++){
       let next = graph[start][i]; 
       if(!visited[next]){
           dfs(next); 
       }
   }
}
let answer = 0; 
for(let i=1; i<=n; i++){
    if(!visited[i]){
        dfs(i);
        answer++;
    }
}
console.log(answer);

의사 코드 추가 

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
let [n, m] = input[0].split(" ").map(Number);

let graph = []; //그래프 생성
for(let i=1; i<=n; i++){ //정점의 수만큼 그래프 생성
    graph[i] = []; 
} 
for(let i=0; i<m; i++){ //1. 연결되어 있는 정점을 그래프로 나타내기 
    let [from, to] = input[i+1].split(" ").map(Number); 
    graph[from].push(to); 
    graph[to].push(from); 
}
let visited = new Array(n+1).fill(false); //방문한 정점 확인하기 위한 그래프 

function dfs(start){ //정점 방문하기 (힌트의 3번에 해당함)
    visited[start] = true; //방문했음
   for(let i=0; i<graph[start].length; i++){ //방문한 그래프의 요소들을 방문하기
       let next = graph[start][i]; //요소가 다음 방문지가 된다.
       if(!visited[next]){ //방문하지 않았다면,
           dfs(next); //방문하러 가자
       }
   }
}
let answer = 0; //연결요소 수 구하기 
for(let i=1; i<=n; i++){ //정점 수 만큼 반복문 돌리기 (힌트의 2번에 해당함)
    if(!visited[i]){ //그 정점을 방문하지 않았다면
        dfs(i); //방문하러 가자
        answer++; 
    }
}
console.log(answer);