자바 코딩테스트 강좌, 연결 요소의 개수 구하기

문제 설명

주어진 그래프에서 연결 요소의 개수를 구하는 문제입니다. 연결 요소란, 그래프에서 어떤 정점들 간에 경로가 존재하는 서브그래프를 의미합니다. 즉, 두 정점 간에 연결되어 있는 경우, 그 정점들은 같은 연결 요소에 속하게 됩니다.

문제 정의

주어진 무방향 그래프의 연결 요소의 개수를 출력하시오.

입력

첫 번째 줄에는 정점의 개수 n (1 ≤ n ≤ 1000)과 간선의 개수 m (0 ≤ m ≤ 10000)이 주어진다. 다음 m개의 줄에는 각 간선의 양 끝 정점 u와 v가 주어진다. u와 v는 서로 다른 정점으로, 정점은 1부터 n까지의 정수로 표현된다.

출력

연결 요소의 개수를 출력하시오.

예제

문제 해결 전략

우선, 문제를 해결하기 위해 다음과 같은 단계를 진행할 것입니다.

그래프를 인접 리스트 형태로 표현합니다.
DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)를 이용하여 연결 요소를 탐색합니다.
탐색하면서 연결 요소의 개수를 카운트합니다.

1. 그래프 표현

우리는 무방향 그래프를 인접 리스트로 표현합니다. 각 정점에는 연결된 정점들의 리스트를 저장합니다. Java에서는 ArrayList를 이용하여 간편하게 구현할 수 있습니다.

2. DFS를 이용한 탐색

그래프를 표현한 후, 각 정점에 대해 DFS를 수행하여 연결된 정점들을 방문합니다. 방문한 정점은 다시 방문하지 않도록 체크할 배열을 사용합니다.

3. 구현 및 결과 도출

총 연결 요소의 개수를 세는 카운터 변수를 두고, 각 정점에 대해 DFS가 시작될 때마다 카운트를 증가시킵니다.

자바 코드 구현


import java.util.ArrayList;
import java.util.Scanner;

public class ConnectedComponents {
    static ArrayList[] graph;
    static boolean[] visited;
    static int count;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt(); // 정점 개수
        int m = scanner.nextInt(); // 간선 개수
        
        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }
        
        count = 0; // 연결 요소 카운트 초기화
        
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                dfs(i); // DFS 실행
                count++; // 새로운 연결 요소 발견 시 카운트 증가
            }
        }
        
        System.out.println(count); // 결과 출력
        scanner.close();
    }

    public static void dfs(int node) {
        visited[node] = true; // 현재 노드 방문 처리
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor); // 인접 노드 탐색
            }
        }
    }
}

코드 설명

위의 Java 코드는 다음과 같은 방식으로 작동합니다:

정점의 개수 n과 간선의 개수 m을 입력받고, 인접 리스트 graph를 초기화합니다.
간선 정보를 입력받아 그래프를 구성합니다.
각 정점에 대해 DFS를 시행합니다. 만약 정점이 방문되지 않았다면, DFS를 호출하여 연결된 모든 정점을 방문합니다.
DFS가 호출될 때마다 연결 요소의 카운트를 증가시킵니다.
최종적으로 연결 요소의 개수를 출력합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n + m)입니다. 여기서 n은 정점의 개수, m은 간선의 개수입니다. DFS를 수행할 때 모든 정점과 간선이 한 번씩 방문되기 때문입니다. 공간 복잡도는 O(n + m)의 추가 공간을 사용하게 됩니다.

결론

연결 요소의 개수를 구하는 문제는 DFS 또는 BFS와 같은 탐색 알고리즘을 통해 해결할 수 있습니다. 이 문제는 그래프에 대한 깊은 이해를 필요로 하며, 문제 해결 과정에 있어서 정확한 그래프 표현과 탐색 방법론을 습득하는 것이 중요합니다. 이를 통해 코딩 테스트에서도 유용한 기초 지식을 쌓을 수 있습니다.

이 강좌를 통해 그래프 이론의 기초와 연결 요소의 개수를 구하는 방법을 배워보았습니다. 앞으로도 다양한 그래프 문제를 풀어보며 알고리즘 실력을 향상시켜 보시기 바랍니다!