백준 11724 : 연결 요소의 개수

💡기본 정보

유형
: DFS/BFS
풀이 날짜
: 2025년 01월 21일 
풀이방법 한줄 요약
: DFS를 활용해 방문했는지 아닌지 확인해서 갯수 세기

 

💡문제에서 구해야 할 것

방향없는 그래프가 주어졌을 때 연결 요소의 개수를 구함
- 입력 : 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어짐 ( 1<=N<=1000, 0<=M<=N(N-1)/2) 
            둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어짐 같은 간선은 한 번만 주어짐
- 출력 : 첫째 줄에 연결 요소의 개수를 출력

 

💡알고리즘 설계

- 그래프를 그린 후 무방향을 정의함

- DFS방식으로 인접리스트를 이용해서 방문하지 않았다면 함수를 재귀

- 방문하지 않은 곳이 있으면 Danswer증가

 

💡CODE

const fs = require("fs");
const input = fs.readFileSync(0,"utf8").toString().split("\n");
const [N,M] = input[0].split(" ").map(Number);

let graph = Array(N+1);
for(let i = 0; i<graph.length;i++){
    graph[i]=[];
}

for(let i = 1; i<=M;i++){
    let[from,to]=input[i].split(" ").map(Number);
    graph[from].push(to);
    graph[to].push(from);
}

const DFSvisit = new Array(N+1).fill(false);
let Danswer = 0;

function DFS(start){
    DFSvisit[start]=true;
    for(const V of graph[start]){
        if(DFSvisit[V]===false){
            DFS(V);
        }
    }
}
for(let i =1;i<=N;i++){
    if (DFSvisit[i]===false){
        DFS(i);
        Danswer++;
    }
}
console.log(Danswer);

 

💡시간복잡도

💡 틀린 이유 & 틀린 부분 수정

처음에는 저번에 풀었던 1260번에서 풀었던 대로 Danswer을 행렬로 정의해서 length를 측정하려고 했는데 그 방법으로 하면 로직도 더 복잡하고 차라리 Danswer을 직접 갯수를 세는 방향으로 수정해서 로직 구현

 

💡 다른 풀이 or 기억할정보

const V of graph[start] 
 : 인접 리스트만 사용해 값만 순회하는 경우에는 이를 사용함

graph[from][to]=1; graph[to][from]=1; 
 : 이 경우에는 무방향 그래프는 맞지만 1차원적으로 표현해서 오류가 발생할 수 있어 
graph[from].push(to); graph[to].push(from); 로 표현해서 사용해야함