[11724] 연결 요소의 개수

✔ 연결 요소의 개수

[백준 11724]

문제 분석하기

노드의 최대 개수가 1000이므로 시간 복잡도 N² 이하의 알고리즘을 모두 사용할 수 있음

연결 요소는 엣지로 연결된 노드의 집합이며, 한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단

손으로 풀어보기

1. 그래프를 인접 리스트로 저장하고 방문 배열도 초기화
   • 이때, 방향이 없는 그래프이므로 양쪽 방향으로 엣지를 모두 저장함
2. 임의의 시작점인 1에서 DFS를 수행
3. 아직 방문하지 않은 노드 중 시작점을 다시 정해 탐색을 진행
4. 모든 노드를 방문한 후 전체 탐색을 종료
   • 총 DFS의 횟수가 연결 요소의 개수가 되게 됨
   • 만약 그래프가 모두 연결되어 있었다면 DFS는 1번 실행되게 됨

슈도코드 작성하기

n(노드 개수) m(에지 개수)
A(그래프 데이터 저장 인접 리스트)
visited(방문 기록 저장 배열)
for(n의 개수만큼 반복하기) {
    A 인접 리스트의 각 ArrayList 초기화하기
}
for(m의 개수만큼 반복하기) {
    A 인접 리스트에 그래프 데이터 저장하기
}

for(n의 개수만큼 반복하기) {
    if(방문하지 않은 노드가 있다면) {
        연결 요소 개수++
        DFS 실행하기
    }
}
연결 요소의 개수를 출력하기

DFS {
    if(현재노드 == 방문노드) return;
    visited 배열에 현재 노드 방문 기록하기
    현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행하기 (재귀 함수 형태)
}

코드 구현하기

/**
 * 11724) 연결_요소의_개수
 */
public class D023_11724 {
    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());
        // n(노드 개수) m(에지 개수)
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        // A(그래프 데이터 저장 인접 리스트)
        A = new ArrayList[n + 1];
        // visited(방문 기록 저장 배열)
        visited = new boolean[n + 1];
        // A 인접 리스트의 각 ArrayList 초기화하기
        for (int i = 1; i < n + 1; i++) {
            A[i] = new ArrayList<Integer>();
        }
        // A 인접 리스트에 그래프 데이터 저장하기
        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 + 1; i++) {
            // 방문하지 않은 노드가 있다면
            if (!visited[i]) {
                // 연결 요소 개수++
                count++;
                // DFS 실행하기
                DFS(i);
            }
        }
        // 연결 요소의 개수를 출력하기
        System.out.println(count);
    }

    static void DFS(int v) {
        // 현재노드 == 방문노드
        if (visited[v]) {
            return;
        }
        // visited 배열에 현재 노드 방문 기록하기
        visited[v] = true;
        // 현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행하기 (재귀 함수 형태)
        for (int i : A[v]) {
            if (visited[i] == false) {
                DFS(i);
            }
        }
    }
}