백준 11724 - 연결 요소의 개수

YongHyun·2023년 4월 17일

Java 백준 코딩테스트

백준, 프로그래머스 - 코딩테스트

목록 보기

23/43

문제

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

입력

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

출력

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

예제 입력 1

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1

2

문제 풀이

DFS(deep first search)문제를 처음으로 접하게 되었는데 문제를 이해하는데 어려움을 겪었었다.

연결 요소 (Connected Component)의 개수 를 구하는 문제인데 이 연결 요소가 무엇인지 전혀 몰랐었다.

찾아보니 연결 요소는 에지로 연결된 노드의 집합이라고 한다. 글로만 보면 이해하기 힘들어서 그림을 첨부하였다.

출처 : https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/
한 번의 DFS 가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소라고 한다.
즉, 여기서는 [0, 1, 2][3, 4] 의 노드 집합이 2개 존재하기 때문에 연결 요소는 2라 할 수 있다.

예제 입력 1에서는 노드의 개수는 6, 에지의 개수는 5이다.

다음으로 에지의 개수만큼 에지의 양끝점인 u와 v를 입력하는데

u = 1, v = 2 가 뜻하는 것은 1번 노드에서 2번 노드로 연결되어 있다는 뜻이다.
u = 2, v = 5 가 뜻하는 것은 2번 노드에서 5번 노드로 연결되어 있다는 뜻이다.
u = 5, v = 1 가 뜻하는 것은 5번 노드에서 1번 노드로 연결되어 있다는 뜻이다.
이렇게 계속 반복해서 입력을 받으면 아래 그림과 같은 형태가 만들어진다.

왼쪽에 있는 그림은 인접 리스트로 노드가 어떠한 방향으로 연결되어 있는지를 보여주고
오른쪽에 있는 그림은 방문 배열이라고 하며 방문했던 노드를 체크해주는 역할을 한다.

여기서 방문 배열이 왜 필요한지 몰랐는데 DFS 는 한 번 방문한 노드를 다시 방문하면 안되기 때문에 체크할 배열이 필요하기 때문이라고 한다.

이제 이를 코드에 적용해보겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class 연결요소의개수 {

    static ArrayList<Integer>[] A;  // 인접 리스트
    static boolean visited[];       // 방문 배열

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());   // 노드 개수
        int M = Integer.parseInt(st.nextToken());   // 에지 개수

        A = new ArrayList[N + 1];                   // 인덱스를 1부터 시작하기 위해서 N + 1 로 지정시켜줌
        visited = new boolean[N + 1];

        for(int i = 1; i < N + 1; i++) {
            A[i] = new ArrayList<>();               // 인접 리스트 초기화
        }
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());   // 시작점
            int E = Integer.parseInt(st.nextToken());   // 끝점
            A[S].add(E);                                // 양방향 에지이므로 양쪽에 추가하기
            A[E].add(S);
        }

        int count = 0;              // 결과를 출력할 변수
        for(int i = 1; i <= N; i++) {
            if(!visited[i]) {       // 방문하지 않은 노드가 없을 때까지 반복
                count++;            
                DFS(i);             //재귀함수 형태의 DFS 함수 구현
            }
        }
        System.out.println(count);

    }

    private static void DFS(int v) {
        if(visited[v])
            return;
        visited[v] = true;
        for(int i : A[v]) {         // 연결 노드 중 방문하지 않았던 노드만 탐색
            if(!visited[i]){
                DFS(i);
            }
        }
    }
}