[백준 / 자바] 11724번 연결 요소의 개수 - DFS

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

11724번: 연결 요소의 개수

문제

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

 

입력

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

6 5 // 노드 개수N, 엣지 개수 M
1 2
2 5
5 1
3 4
4 6

 

출력

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

2

 

풀이

시간 제한은 3초

N의 최대 값은 1000으로 N^2이하 알고리즘 모두 가능

DFS를 이용해 풀어봄

 

연결 요소는 엣지로 연결된 노드의 집합을 의미

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

 

① 초기

노드	인접 리스트
1	2	5
2	1	5
3	4
4	3	6
5	2	1
6	4

방향이 없는 그래프이기 때문에 양쪽 방향으로 모두 엣지 저장(3 노드를 보면 3 ↔ 4)

1	2	3	4	5	6
F	F	F	F	F	F

방문 배열 생성

 

② DFS 1차

노드	인접 리스트
1	2	5
2	1	5
3	4
4	3	6
5	2	1
6	4

1	2	3	4	5	6
T	T	F	F	T	F

 

1에서 시작해 연결된 노드를 방문 → 방문전 방문 여부 확인 후 방문 → 방문 배열을 수정

1 → 2 → 5 순으로 탐색

 

③  DFS 2차

노드	인접 리스트
1	2	5
2	1	5
3	4
4	3	6
5	2	1
6	4

1	2	3	4	5	6
T	T	T	T	T	T

 

아직 방문하지 않는 노드가 있어 시작점을 다시 설정 후 탐색

3에서 시작해 연결된 노드를 방문 → 방문전 방문 여부 확인 후 방문 → 방문 배열을 수정

3 → 4 → 6 순으로 탐색 → 방문하지 않은 노드 없음(방문 배열 모두 T) → 탐색 종료

 

총 2번의 DFS가 진행 → 2개의 연결 요소 개수

 

# 코드

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

public class Main {
    static boolean visited[]; // 방문 배열
    static ArrayList<Integer>[] a; // 인접 리스트
    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()); // 엣지 개수

        visited = new boolean[n+1];
        a = new ArrayList[n+1];

        // 인접 리스트 데이터
        for(int i = 1; i < n+1; i++) {
            a[i] = new ArrayList<>();
        }

        // 인접 리스트 데이터 저장
        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; // 연결 요소 개수

        // 방문하지 않은 노드가 있으면 count++, DFS()함수 호출
        for(int i = 1; i < n+1; i++){
            if(!visited[i]) {
                count++;
                DFS(i);
            }
        }

        System.out.println(count);

    }

    private static void DFS(int n) {
        if(visited[n]) return; // 방문한 노드이면 탐색하지 않음

        // 방문하지 않은 노드면 방문
        visited[n] = true;

        // 현재 노드 n의 인접 리스트에서 방문하지 않는 노드 방문
        for(int i : a[n]) {
            if(!visited[i]) DFS(i);
        }
    }
}