[Baekjoon] 11724 - 연결 요소의 개수

📝 문제

 

 

❗ 주의

ArrayList형 배열 A를 사용하기 전에

각 요소를 초기화 시켜줘야 한다.

 

 

 

🔑 풀이 과정

· 연결 요소(Connected Component): 무방향 그래프에서 서로 다른 두 정점이 경로로 연결되어 있으면서 상위 그래프의 추가 정점이 없는 부분 그래프

→ 말이 어려울 수 있는데, 그림으로 그렸을때 한 덩어리가 연결 요소이다.

해당 문제 예시 1, 2를 그림으로 표현하면 다음과 같다.

예시 1은 덩어리가 2개 = 연결 요소 2개

예시 2는 덩어리가 1개 = 연결 요소 1개

ArrayList를 사용하여 그래프를 인접리스트로 표현해주었다.

또한 방문 배열을 생성해서 방문시 true, 아직 방문하지 않았으면 false로 표현

 

이 문제 풀이를 위해 깊이 우선 탐색(DFS)를 사용할 것이다.

한 번의 DFS를 진행하면서 탐색한 모든 노드는 같은 연결요소에 있다.

= 하나의 노드를 DFS 하면 같은 연결요소에 있는 노드들을 탐색하므로, 방문배열이 true가 된다.

 

노드 수 만큼 for문을 돌리면서 방문배열이 false인 경우(탐색되지 않은 경우) count를 증가시켜준다.

 

 

 

🔓 답안

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<Integer>[] A;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        A = new ArrayList[N+1];
        visited = new boolean[N+1];

        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 u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            A[u].add(v);
            A[v].add(u);
        }


        int count = 0;
        for(int i = 1; i <= N; i++){
            if(!visited[i]){
                count++;
                DFS(i);
            }
        }

        bw.write(count + "\n");
        bw.flush();
        bw.close();
    }

    static void DFS(int s){
        if(visited[s]){
            return;
        } else{
            visited[s] = true;
            for(int r : A[s]){  // 나중에는 visited[r]이 false인 경우에만 DFS를 실행하게 작성해주자
                DFS(r);
            }
        }
    }

}

 

 

 

🖤 알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

- 깊이 우선 탐색