[백준 11724]연결 요소의 개수 (Java)

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

연결 요소의 개수

문제

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

입력

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

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()); // 1번째 줄 읽음

        int N = Integer.parseInt(st.nextToken()); // 노드 개수
        int E = Integer.parseInt(st.nextToken()); // 엣지 개수 (노드 연결리스트 개수)

        visited = new boolean[N+1]; // 노드 1부터 시작하므로 N+1 크기 선언
        A = new ArrayList[N+1];// 노드 1부터 시작하므로 N+1 크기 배열선언

        // 노드 개수만큼 각 노드에 연결리스트 연결
        for(int i=1; i<N+1; i++){
            A[i] = new ArrayList<Integer>();
        }

        // 연결리스트 구현
        for(int i=1; i<E+1; i++){ // 엣지 갯수만큼 순회, 양방향 연결
            st = new StringTokenizer(br.readLine()); // 2 ~ E번째 줄 읽음
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());

            A[node1].add(node2); // 노드 양방향 연결
            A[node2].add(node1);
        }

        int DFScount = 0; // DFS 순회 횟수

        for(int i=1; i<N+1; i++){
            // 노드 1번 부터 순회
            if(!visited[i]){
                // 아직 방문하지 않은 노드가 있다면 DFS 실행
                DFScount++;
                DFS(i);
            }
        }
        System.out.println(DFScount);
    }

    private static void DFS(int i) {
        // i번 노드 DFS 탐색
        if(visited[i]){
            return; // 만약 i번 노드를 탐색해봤다면 탐색종료
        }

        // 아직 방문한적 없는 노드라면 방문체크 후 DFS 탐색수행
        visited[i] = true;
        for(int node : A[i]){
            // i번 노드에 딸려있는 인접 리스트 순회
            if(!visited[node]){
                // 딸려있는 인접 노드 방문하지 않았다면 DFS 수행
                DFS(node);
            }
        }
    }
}

 

• DFS 기본문제
• 깊이우선 탐색을 하면서 모든 노드를 방문하기 위해서 DFS 를 몇번 수행해야하는지 구하는 문제이다.
• ArrayList 배열에 특정 노드에 인접한 인접노드 번호를 저장하기 위해 각 노드 별로 연결리스트를 구현해준다.
• 양방향 연결 그래프이므로 2번째줄 부터 읽어들인 노드번호를 서로 양쪽에 저장해준다.
• 모든 노드를 방문할때까지 DFS 를 수행한다.