[백준]연결요소의개수

해설

 

1. 그래프 인접 리스트로 저장, 방문 배열 초기화.
방향이 없는 그래프 라서 양쪽 방향으로 에지를 모두 저장한다.

 

 

2.임의의 시작점에서 DFS를 수행한다.

현재의 경우 1을 시작점으로 정함. 탐색을 마친 이후 방문한 곳은 1,2,5가 된다.

 

 

3.아직 방문하지 않은 노드가 있으므로 시작점을 다시 정해 탐색을 진행.

현재의 경우 3,4,5, 순서로 탐색을 마침. 모든 노드를 방문했으니 전체 탐색을 종료.

 

 

4.1~3 과정을 통해 총 2번의 DFS가 진행되었다. 즉 연결 요소 개수는 2개이다.

 

모든 노드를 탐색하여 탐색 종료 -> DFS 총 2회 수행

*연결 요소 개수 = 2

 

만약 그래프가 모두 열결 되어있었다면 DFS는 1번 실행되었을 것이다.

다시말해 모든 노드를 탐색하는 데 실행한 DFS의 실행 횟수가 곧 열결 요소 개수와 같다.

 

슈도코드

 

코드

package 백준.복습;

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

public class 연결요소의개수DFS {

    static List<Integer>[] A; // 그래프의 인접 리스트를 저장할 배열
    static boolean[] visited; // 각 노드의 방문 여부를 체크할 배열

    public static void main(String[] args) throws IOException {

        //1. n(노드 개수) m(엣지 개수) 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(stringTokenizer.nextToken()); // 노드의 개수
        int m = Integer.parseInt(stringTokenizer.nextToken()); // 엣지의 개수

        //2. A(그래프 데이터 저장 인접 리스트 배열 초기화)
        A = new ArrayList[n+1]; // n+1 크기의 ArrayList 배열 초기화
        visited = new boolean[n+1]; // n+1 크기의 boolean 배열 초기화

        //2-2. 그안에 ArrayList 생성
        for (int i = 1; i < n+1 ; i++) {
            A[i] = new ArrayList<>(); // 각 인덱스에 ArrayList 할당
        }

        //3. 인접 리스트에 그래프 데이터 저장하기
        for (int i = 0; i < m ; i++) {
            stringTokenizer = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(stringTokenizer.nextToken());
            int e = Integer.parseInt(stringTokenizer.nextToken());
            A[s].add(e); // 노드 s와 e를 연결
            A[e].add(s); // 노드 e와 s를 연결 (양방향)
        }

        // 저장된 값 보기 (스트림을 사용한 출력)
        Arrays.stream(A)
                .filter(list -> list != null) // null이 아닌 리스트만 처리
                .forEach(list -> {
                    list.forEach(item -> System.out.print(item + " ")); // 리스트의 요소 출력
                    System.out.println(); // 줄바꿈
                });

        int count = 0; // 연결 요소의 개수를 저장할 변수

        // 모든 노드에 대해 DFS 실행하여 연결 요소 개수 계산
        for (int i = 1; i < n+1 ; i++) {
            if(!visited[i]){ // 노드 i가 방문되지 않았다면
                count++; // 연결 요소의 개수 증가
                DFS(i); // DFS 실행
            }
        }
        System.out.println("answer = " + count); // 결과 출력
    }

    // DFS 메소드
    private static void DFS(int v) {
        if(visited[v]){ // 이미 방문한 노드라면 리턴
            return;
        }
        visited[v] = true; // 노드 v를 방문 처리

        for (int i: A[v]) { // 노드 v와 연결된 모든 노드에 대해
            if(!visited[i]) { // 아직 방문하지 않은 노드라면
                DFS(i); // 해당 노드에 대해 DFS 실행
            }
        }
    }
}