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

문제: https://www.acmicpc.net/problem/11724

📌 문제 탐색하기

입력 : 첫째 줄 - 정점의 개수 N, 간선의 개수 M (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
둘째 줄 - 간선의 양 끝점 u, v (1 ≤ u, v ≤ N, u ≠ v)
둘째 줄이 M만큼 반복
출력 : 연결 요소의 개수

가능한 시간복잡도

O(N)

알고리즘 선택

그래프 탐색

📌 코드 설계하기

1. 정점의 개수 N, 간선의 개수 M을 입력받는다.
2. 간선의 양 끝점 u, v를 입력받아 인접 리스트를 채운다.
3. dfs 함수는 주어진 노드와 연결된 모든 노드를 재귀적으로 방문하도록 설정한다.
4. 각 노드에 대해 해당 노드가 방문되지 않았다면 dfs를 실행하고, 연결 요소의 개수를 증가시킨다.
5. 연결 요소의 개수를 출력한다.

📌 시도 회차 수정 사항 (Optional)

💡 시도별 수정 사항은 어떻게 작성하나요?
- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

1회차

2회차

📌 정답 코드

import java.util.*;

public class Main {
    static List<List<Integer>> graph;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        visited = new boolean[N + 1];
        int count = 0;

        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                dfs(i);
                count++;
            }
        }

        System.out.println(count);
    }

    static void dfs(int node) {
        visited[node] = true;
        for (int next : graph.get(node)) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }
}