[BAEKJOON] - 11724번 : 연결 요소의 개수

11724번 문제 링크

⌛시간 복잡도

• 1초에 1억번 = 3초에 3억번 가능.
• 제한 조건 : N(노드) 갯수 1,000개
• O(N^2) 이하 사용 가능.

📜로직

1. 인접 리스트의 각 ArrayList 초기화
2. 인접 리스트에 그래프 값을 저장
3. 인접 리스트 항목 중 방문여부 확인 후 방문하지 않은 경우 counting
4. DFS 실행
   • 방문 여부 확인
   • 방문 true
   • 인접 리스트 내 담긴 인접 노드들의 방문여부 확인 후 재귀 호출

☢️ 주의할 점

• 그래프의 연결 방향이 없기 때문에, 양방향으로 저장해줘야 한다.

ex)

• 1- 2 인 경우, 인접 리스트[1] 에 '2' 저장 and 인접 리스트[2]에 '1' 저장.

😀 성공

import java.io.*;
import java.util.*;

public class Main{
    static boolean[] visited;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int node = Integer.parseInt(str[0]);
        int edge = Integer.parseInt(str[1]);
        ArrayList<Integer>[] li = new ArrayList[node + 1]; // 인접 리스트
        visited = new boolean[node + 1]; // 방문 배열
        int linkedFactor = 0;
        
        // 인접 리스트 초기화
        for(int i=1; i <= node; i++){
            li[i] = new ArrayList<Integer>();
        }
        
        // 인접 리스트에 그래프 값 대입
        for(int i=0; i < edge; i++){
            str = br.readLine().split(" ");
            int u = Integer.parseInt(str[0]);
            int v = Integer.parseInt(str[1]);
            li[u].add(v);
            li[v].add(u);
        }
        br.close();
        
        // 방문 여부 확인 후 dfs 호출
        for(int i=1; i <= node; i++){
            if(!visited[i]){
                linkedFactor++;
                dfs(li, i);
            }
        }
        System.out.println(linkedFactor);
    }
    
    // 깊이 우선 탐색
    static void dfs(ArrayList<Integer>[] li,int node){
        if(visited[node])
            return;
        
        visited[node] = true;
        
        if(li[node].isEmpty())
            return;
        
        for(int j = 0; j < li[node].size(); j++){
            int idx = li[node].get(j);
            if(!visited[idx])
                dfs(li,idx);
        }
    }
}