연결 요소의 개수 (백준 11724) - DFS

문제분석

• 노드 최대 개수가 1,000이므로 시간복잡도 n² 이하의 알고리즘 사용가능
• 연결 요소는 엣지로 연결된 노드의 집합이므로, 한번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합 = 하나의 연결 요소

손으로 풀어보기

1. 인접리스트, 방문배열 생성
2. 임의의 시작점에서 DFS 수행
   

• 1 -> 2 -> 5 끝

3. 아직 방문하지 않은 노드부터 시작점을 다시 정해 탐색 진행
   

• 3 -> 4 -> 6 끝

4. 방문배열이 모두 T로 바뀌었으므로, 총 2번의 DFS진행 = 연결요소개수 2개

슈도코드

정답

package A0study;

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

public class p11724_연결요소의개수 {
    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];       // 0번 인덱스 사용X (1번 인덱스부터 시작)
        visited = new boolean[N+1];

        // 인접리스트의 각 ArrayList 초기화
        for(int i=1; i<=N; i++) {
            A[i] = new ArrayList<Integer>();
        }

        // 인접리스트에 그래프 데이터 저장
        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);
            }
        }
        System.out.println(count);
    }

    // DFS
    private static void DFS(int v) {
        if(visited[v]) {
            return;
        }
        visited[v] = true;  // 방문처리
        for(int i : A[v]) {     // A[v] 안에 들어있는 모든 값을 하나씩 i에 꺼내서 반복한다
            if(!visited[i]) {
                DFS(i);
            }
        }
    }
}