<코테 챌린지> 연결 요소의 개수 (백준 11724번)

❓ 문제

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

📥 입력

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

📤 출력

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

📥 예제 입력

📤 예제 출력

👩🏻‍💻 내 코드

package baekjoon.코테챌린지;

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

public class 연결요소의개수 {

    // DFS 함수
    public static void DFS(ArrayList<ArrayList<Integer>> graph, int v, boolean[] visited) {
        visited[v] = true; // 현재 정점 방문 처리

        // 현재 정점과 연결된 다른 정점들에 대해 DFS 재귀 호출
        for (int neighbor : graph.get(v)) {
            if (!visited[neighbor]) {
                DFS(graph, neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int n = in.nextInt(); // 정점의 개수
        int m = in.nextInt(); // 간선의 개수

        // 그래프를 저장할 인접 리스트
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선
        for (int i = 0; i < m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            graph.get(u).add(v);
            graph.get(v).add(u); // 무방향 그래프이므로 양방향으로 추가
        }

        // 방문 여부를 저장할 배열
        boolean[] visited = new boolean[n + 1];

        int count = 0; // 연결 요소의 수를 카운트

       
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                DFS(graph, i, visited); // 방문하지 않은 정점은 DFS 수행
                count++; // DFS가 끝나면 연결 요소 하나를 발견한 것
            }
        }
        System.out.println(count);
    }

}

💡 코드 접근

그래프 저장
- 인접 리스트(ArrayList<ArrayList<Integer>>)를 사용하여 그래프의 각 정점과 연결된 정점들을 저장한다.
- 그래프의 정점의 개수 n과 간선의 개수 m을 입력받고, 간선 정보를 통해 각 정점과 연결된 다른 정점들을 리스트로 관리한다.
DFS(깊이 우선 탐색) 탐색
- DFS는 현재 정점에서 연결된 정점을 재귀적으로 방문하면서 모든 연결된 정점을 탐색하는 방법
- 방문하지 않은 정점에 대해 DFS를 시작하고, 탐색된 모든 정점은 visited 배열을 통해 방문 기록을 저장한다.
  - 모든 정점에 대해 DFS를 실행하면서, 방문하지 않은 정점에서 새로운 DFS를 시작해 연결 요소를 찾는다.
- DFS가 끝날 때마다 연결 요소 하나를 찾았다고 보고, 연결 요소의 개수를 증가시킨다.
- DFS가 끝날 때마다 하나의 연결 요소가 탐색되었으므로 count 변수를 증가시키는 방식으로 총 연결 요소의 개수를 계산한다.

💡 배울점

ArrayList

자바의 ArrayList는 동적 배열로, 크기를 미리 정하지 않고 필요에 따라 크기가 자동으로 조절되는 리스트이다.

ArrayList<ArrayList<Integer>>

이 구조는 "리스트의 리스트”
한마디로, 2차원 배열처럼 동작하지만 크기가 동적으로 변할 수 있다.
각 내부의 ArrayList<Integer>는 특정 정점에 연결된 다른 정점들을 저장하는 용도로 사용된다.
- 그래프에서 정점과 간선의 관계를 저장할 때, 각 정점이 어떤 정점들과 연결되어 있는지를 저장해야 하는데, 이 때 각 정점에 연결된 정점들의 목록을 리스트로 표현하는 것이 인접 리스트 방식
왜 ArrayList<ArrayList<Integer>>를 사용?
- 정점의 개수와 각 정점에 연결된 간선의 수가 가변적이기 때문에, 고정 크기의 2차원 배열 대신 동적으로 크기를 조정할 수 있는 ArrayList가 적합
- 그래프의 간선 정보를 저장하는 대표적인 방법 중 하나가 인접 리스트 방식
  - 예를 들어, 정점 u와 v가 연결되었다면 graph[u] 리스트에 v를 추가하고, graph[v] 리스트에 u를 추가하는 방식으로 그래프의 연결 상태를 저장할 수 있음
- ArrayList<ArrayList<Integer>>는 각 정점에 대해 연결된 정점들의 리스트를 저장하기 때문에, 무방향/방향 그래프의 간선 정보를 효율적으로 저장할 수 있기에 사용하기 적합.

저작자표시 비영리 변경금지

Today I Learned