[백준][자바(java)][dfs] #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와 BFS가 있지만, DFS를 이용해서 풀어보려고 한다.

DFS설명 : zionyy.tistory.com/14

---

 

인접 행렬을 사용해주기 위해 int map[][]과 방문 여부를 저장해주기위한 int visit[]을 선언해준다.

 

무방향 그래프이기 때문에 그래프를 입력받을 때, 양쪽을 다 1로 저장해주어야한다.

for(int i = 0; i < e; i++) {
	int v1 = sc.nextInt();
	int v2 = sc.nextInt();
			
	map[v1][v2] = map[v2][v1] = 1;
}

연결 요소의 경우 한방향으로 진행하는 DFS를 이용한다면, 더이상 진행 할 수 없는 상황에 도달했을 때, 더이상의 갈림길이 없어 재귀가 끝나게 되고 그 지점이 바로 하나의 연결 요소가 끝나게 되는 지점인 것이다. 

그림으로 보면 다음과 같다.

1부터 시작하는 dfs를 진행하면 1 → 2 → 5 까지 순차적으로 잘 이동하고 5에서의 갈림길을 확인하면 1은 이미 방문했고 1외에는 다른 갈림길이 없기 때문에 재귀가 끝나게 되는 것이다. 그렇다면 1-2-5가 연결된 연결 요소가 탄생하는 것이다. 이를 이용하여 연결 요소의 개수를 구하는 코드를 작성해보자.

---

import java.util.Scanner;
 
public class Main{
    static final int MAX_VERTEX = 1001;
     
    static int map[][] = new int[MAX_VERTEX][MAX_VERTEX];
    static int visit[] = new int[MAX_VERTEX];
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int e = sc.nextInt();
        int result = 0;
        
        for(int i = 0; i < e; i++) {//무방향 그래프
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            
            map[v1][v2] = map[v2][v1] = 1;
        }
        
        for(int i = 1; i <= n; i++) {
            if(visit[i] == 0) {//방문을 하지 않은 노드부터 시작
                depthFirstSearch(i,n);
                result++;
            }
        }
        
        System.out.println(result);
    }
    
    static void depthFirstSearch(int v, int n)
    {
        visit[v] = 1;//방문함
        for (int i = 1; i <= n; i++)
        {
            if (map[v][i] == 1 && visit[i] == 0)
            {
                depthFirstSearch(i, n);
            }
        }
    }
}
 

---

<참고 자료>
velog, "연결 요소 (Connected Component)", https://velog.io/@polynomeer/%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8CConnected-Component