[DFS 문제] 그래프 탐색 / 연결 요소의 개수 찾기

그래프 탐색 (예상 소요 시간: 15~20분)

🔹 문제: 연결 요소의 개수 찾기

 

N개의 노드와
M개의 간선이 있는 무방향 그래프에서 연결 요소(연결된 노드 집합)의 개수를 구하시오.

 

입력 예시:

      
      
      
    
console.log(solution(6, [
    [0, 1],
    [0, 2],
    [3, 4]
]));  // 출력: 3

 

 

풀이

1. 6개의 노드가 있고, 간선으로 연결된 노드는 아래와 같다:
   • 0-1-2 (하나의 연결 요소)
   • 3-4 (두 번째 연결 요소)
   • 5는 독립적으로 존재 (세 번째 연결 요소)
2. 방문하지 않은 노드부터 DFS나 BFS를 시작하고, 그 노드와 연결된 모든 노드를 탐색한다.
3. 각 연결 요소를 찾을 때마다 연결 요소 개수를 증가시킨다.

      
      
      
    
function solution(n, edges) {
    let count = 0;
    
    // 그래프 만들기
     let graph = Array.from({length:n},()=>[]);
    for(let [a, b] of edges){
        graph[a].push(b);
        graph[b].push(a);
    }

    let visited = Array.from({length:n},()=>false); // // 방문 여부 체크
    
    function dfs(node){
        visited[node] = true; // 현재 노드 방문 처리
        for(let neighbor of graph[node]){
            if(!visited[neighbor]){
                dfs(neighbor); // 연결된 노드도 DFS 탐색
            }
        }
    }

  	// 모든 노드를 탐색하면서 연결 요소 개수 찾기
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {  // 아직 방문하지 않았다면
            componentCount++;  // 새로운 연결 요소 발견
            dfs(i);  // 연결 요소를 DFS로 탐색
        }
    }
    
}

console.log(solution(6, [
    [0, 1],
    [0, 2],
    [3, 4]
]));  // 출력: 3

 

 

핵심 설명

1. 그래프 만들기:
   • 간선 리스트를 기반으로 그래프를 인접 리스트 형식으로 구성한다.
2. DFS:
   • DFS를 시작하고, 연결된 모든 노드를 방문 처리한다.
3. 연결 요소 세기:
   • 방문하지 않은 노드가 있으면, 그 노드부터 DFS를 시작해서 연결된 모든 노드를 방문하고, 그때마다 연결 요소의 개수를 증가시킨다.

결과

이 코드는 연결 요소의 개수를 출력한다.
예시에서 3개의 연결 요소가 있으므로 출력은 3이다.

---

핵심 포인트

• 연결 요소는 연결된 노드들을 의미하고, DFS나 BFS로 연결된 모든 노드를 탐색하면서 그룹화할 수 있다.
• 각 연결 요소를 찾을 때마다 연결 요소 개수를 증가시킨다.