[Java | 백준 11724번] 연결 요소의 개수

백준 11724번 www.acmicpc.net/problem/11724

 

 

연결요소(Connected Component)

 

아래 사진에서 보면 등가관계의 구성요소가 총 3개임을 알 수 있다. 즉, 연결요소 또는 구성요소가 3개 있다고 표현한다.

그래프에서 하나의 노드에서 출발해서 연결된 그래프가 하나의 연결요소이자, 이 전체를 3개의 구성요소로 된 하나의 그래프라고도 표현할 수 있다.

 

위키백과 구성요소

 

 

풀이

 

DFS, BFS 풀이가 모두 가능하다. 아래 풀이는 DFS 풀이이다.

 

1. 일단 변수들을 초기화해준다.

num 은 정점의 수, path는 간선의 수, node 는 실제 간선의 양 끝점을 확인하는 boolean 값, visit 는 방문여부를 표시한다.

cnt 는 visit 값이 false 일 때, 그 수를 세어준다.(출력값)

 

2. 방향성이 없는 그래프 이동으므로 node[n][m] 값과 node[m][n] 모두 true; 값을 준다.

 

3.  static void path(int x) 메서드를 먼저 살펴보자. 메서드의 실행은 visit[x] 값이 false 일 때 실행되는데 방문하지 않은 간선이므로, visit[x] 를 true 로 바꿔준다. 그리고 node[x][i] 값이 있으나 visit[x] 값이 false 라면, 즉 연결된 노드인데 방문하지 않았다면 다시 재귀형태로 path() 메서드를 실행한다.

정리하자면 연결된 간선이 있고 방문하지 않았다면 다 방문할 수 있도록 하는 것이다.

 

4. 3 번의 내용처럼 연결된 간선을 따라 방문하면 true 가 되므로  DFS_11724 클래스의 for 문에서는 방문하지 않은 경우를 발견했을 때, cnt 를 세면서 연결 요소의 개수를 파악할 수 있다.

 

 

import java.util.Scanner;
 
public class DFS_11724 {
    static int num = 0, path = 0;
    static boolean[][] node = new boolean[num+1][num+1];
    static boolean[] visit = new boolean[num+1];
    static int cnt = 0;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int path = sc.nextInt();
                
        for (int i=0; i<num; i++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            node[n][m] = true;
            node[m][n] = true;            
        }
        
        for (int i=1; i<=num; i++) {
            if (!visit[i]) {
                path(i);
                cnt++;
            }
        }
 
        System.out.println(cnt);
        sc.close();    
    }
    
    static void path(int x) {
        visit[x]=true;
        
        for(int i=1; i<=num; i++) {
            if (node[x][i] && !visit[i]) {
                path(i);
            }
        }
    }
        
}