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

문제

✔ 난이도 - Silver 2

설명

DFS 간단 정리 참고

방향이 없는 그래프이므로 간선을 양쪽 방향으로 모두 저장해야함.

우선 러프하게 생각해보자면,
어떤 노드B가 방문되었다는건 현재 내 노드A와 그 어떤 노드B가 연결되어 있다는 뜻이다. 즉, '연결 요소'라는 뜻.
main에서 1~N까지 돌아가면서 연결 간선을 체크하는데, 현재 방문하지 않은 노드라면 새로운 '연결 요소' 덩어리가 하나 생성되었다는 뜻이다.

좀 더 자세히 설명해보겠다.

처음에 노드 1을 검사한다. 1과 연결된 상대 노드들을 쭉 돌면서 상대 노드들을 다 visited로 만든다. 즉, 노드 1과 연결된 '연결 요소'라고 적어놓는 것이다. 그런데 이 때 상대 노드와 연결된 또 다른 노드가 있을수도 있으니 재귀로 또 다시 dfs를 부른다.
이렇게 되면 노드 1과 연결된 하나의 큰 덩어리의 '연결 요소'가 생긴다.

완료 된 후에 dfs를 빠져나오면 이제는 노드 2를 검사한다. 노드 2가 이전의 '연결 요소'에 포함되었다면 즉, visited 상태면 dfs를 안탄다.

만약 노드 i가 not visited 상태면? 이전의 '연결 요소'에 포함되지 않은 노드라는 뜻이다. 해당 덩어리에 포함되지 않은 노드이므로 새로운 new '연결 요소'가 생성되는 것이다.
따라서 이렇게 not visited인 상태에 대해서 count++을 해준다.

풀이 (재귀)

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        ArrayList<Integer>[] graph = new ArrayList[N+1];

        for (int i = 1; i <= N; i++){
            graph[i] = new ArrayList<>();
        }
       
        for (int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            graph[start].add(end);
            graph[end].add(start);
        }
        // ----------- 간선 저장 끝

        boolean[] visited = new boolean[N+1];

        int count = 0;

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

        sb.append(count);
        System.out.print(sb);
    }

    private static void dfs(int node, ArrayList<Integer>[] graph, boolean[] visited) {
        visited[node] = true;

        for(int dest: graph[node]){
            if (!visited[dest]){
                dfs(dest, graph, visited);
            }
        }

        return;
    }
}

⏰ 시간복잡도

$O(N + M)$

$N$은 정점(노드)의 개수이고, $M$은 간선의 개수
알고리즘 문제 풀이에서 DFS/BFS의 시간 복잡도를 계산할 때는 각 노드와 간선을 몇 번씩 건드리는가를 보면 됨.

1. 그래프 생성 (초기화 및 간선 저장)

• ArrayList<Integer>[] graph = new ArrayList[N+1];
• for (int i = 1; i <= N; i++){ graph[i] = new ArrayList<>(); }
  • $N$개의 정점에 대해 인접 리스트를 초기화하므로 $O(N)$
• for (int i = 0; i < M; i++){ ... }
  • $M$개의 간선을 입력받는다.
  • graph[start].add(end);와 graph[end].add(start);는 ArrayList의 맨 끝에 추가하는 연산이므로 평균 $O(1)$
  • 따라서 $M$개의 간선을 양방향으로 저장하는 데 총 $O(M)$이 걸림

그래프 생성까지의 시간: $O(N + M)$

2. 그래프 탐색 (DFS)

• for (int i = 1; i <= N; i++){ ... }
  • 1번부터 $N$번까지 모든 정점을 확인하는 바깥쪽 루프
• if (!visited[i]){ dfs(i, ...); }
• dfs() 함수 내부
  • DFS는 방문한 정점을 다시 방문하지 않음
  • 따라서 바깥쪽 for문을 포함하여 dfs 함수가 실행되는 총 과정 동안, 모든 정점($N$개)은 정확히 한 번씩만 방문한다. -> $O(N)$
  • for(int dest: graph[node])
    • dfs가 모든 정점을 방문하는 동안, 각 정점에 연결된 모든 간선을 확인한다.
    • 양방향으로 간선을 저장했으므로, 인접 리스트의 모든 항목 수는 총 $2M$개.
    • 즉, 모든 간선($M$개)을 양방향으로 한 번씩, 총 두 번 확인하게 된다. ($O(2M) \rightarrow O(M)$)

그래프 탐색의 총 시간: $O(N + M)$

두 과정을 합친 총 시간 복잡도는 $O(N + M) + O(N + M)$ 이며, 빅오 표기법에 따라 $O(N + M)$이 된다.

시간 제한이 3초일때 통과할 수 있을까?

1. 알고리즘 시간 복잡도: $O(N + M)$
2. 시간 제한: 3초 (약 3억 번의 연산 가능)
3. 최대 제약 조건 (Worst Case):
   ◦ $N$ (정점): 1,000
   ◦ $M$ (간선): $N \times (N-1) / 2 = (1,000 \times 999) / 2 \approx$ 500,000 (약 50만)

총 연산 횟수 계산

알고리즘의 총 연산 횟수는 $N + M$에 비례한다.총 연산 횟수 $\approx$ (최대 $N$) + (최대 $M$)
$\approx$ 1,000 + 500,000
$\approx$ 501,000 (약 50만 번)

충분하다.

풀이 (stack)

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        ArrayList<Integer>[] graph = new ArrayList[N+1];
        for (int i = 1; i <= N; i++){
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a].add(b);
            graph[b].add(a);
        }

        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[N+1];
        int count = 0;

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

            stack.push(i);
            visited[i] = true;
            count++;

            while (!stack.isEmpty()){
                int node = stack.pop();
                for (int n : graph[node]){
                    if (!visited[n]){
                        stack.push(n);
                        visited[n] = true;
                    }
                }
            }
        }

        sb.append(count);
        System.out.println(sb);
    }
}

⏰ 시간복잡도

$O(N + M)$
$N$: 정점의 개수, $M$: 간선의 개수

알고리즘 문제 풀이에서 DFS/BFS의 시간 복잡도를 계산할 때는 각 노드와 간선을 몇 번씩 건드리는가를 보면 됨.

1. 정점(Node) 방문: $O(N)$

• for (int i = 1; i <= N; i++) 루프를 통해 모든 노드를 한 번씩 확인
• visited[i] 배열 덕분에, 어떤 노드든 stack에 들어갔다가 pop되는 과정은 정확히 한 번씩만 일어난다.
• 즉, 모든 정점을 방문하는 데 드는 시간은 $N$에 비례함

2. 간선(Edge) 확인: $O(M)$

• while문 안의 for (int n : graph[node]) 부분을 보면 특정 노드가 pop되었을 때, 그 노드와 연결된 간선들을 하나하나 검사한다.
• 전체 탐색 과정 동안 모든 노드가 한 번씩 pop되므로, 결과적으로 그래프에 존재하는 모든 간선을 확인하게 된다.
• 무방향 그래프이므로 각 간선은 양쪽 끝에서 한 번씩, 총 두 번 확인되지만 이는 상수를 무시하는 빅오 표기법상 $O(M)$ 가 됨

3. 총합: $O(N + M)$

• 모든 정점을 방문($N$)하고, 각 정점에서 연결된 모든 간선을 확인($M$)하므로 최종 복잡도는 $O(N + M)$