[백준 - 11724] 연결 요소의 개수 .java

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

 

Solution

노드 최대 개수가 1,000이므로 시간 복잡도 n^2이하의 알고리즘 모두 사용 가능!

연결 요소 = 에지로 연결된 노드의 집합

1개의 연결 요소  =  한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합

 

 

 

 

• boolean 배열

기본적으로 false로 초기화

->  visited = new boolean[n+1]; 코드 실행 후, visited 배열의 모든 요소는 자동으로 false로 설정.

 

• nums 배열

ArrayList[] 타입의 배열 -> 즉, ArrayList 객체를 저장

각 인덱스는 그래프의 노드를 나타내고, 각 인덱스에 연결된 ArrayList는 그 노드와 연결된 노드들을 저장

-> 예를 들어, nums[1]은 노드 1과 연결된 모든 노드들을 저장하는 ArrayList이고, nums[2]는 노드 2와 연결된 모든 노드들을 저장하는 ArrayList.

 

• new ArrayList<Integer>()

nums[i] = new ArrayList();는 노드 i에 대한 인접 리스트를 초기화 

-> ArrayList는 노드 i와 연결된 다른 노드들의 리스트를 저장하는 데 사용.

-> 새로운 ArrayList 객체가 생성되고, nums[i]에 할당

 

연결요소가  dfs의 실행 회수임을 아는 게 중요한 문제였다.

 

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

public class Main {
    static ArrayList<Integer>[] nums;
    static boolean visited[];

    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()); // 에지 개수

        //노드 시작은 1부터
        nums = new ArrayList[n+1];
        visited = new boolean[n+1];

        //인접 리스트 초기화
        for(int i = 1; i <= n; i++) {
            nums[i] = new ArrayList<Integer>();
        }

        //입력 받은 노드들 저장
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            //입력 받은 두 양 끝점
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            //무방향 그래프니까 양쪽 다 연결시키기~
            nums[s].add(e);
            nums[e].add(s);
        }
        //dfs 실행 횟수
        int count = 0;

        //노드들 차례대로 방문
        for(int i = 1; i <= n; i++) {
            //방문 안한 노드가 없을때까지 반복
            if(!visited[i]) {
                count++; //실행 증가
                DFS(i);
            }
        }

        System.out.println(count);

    }

    static void DFS(int v) {
        //방문 한거면
        if(visited[v]) {
            return;
        }
        //방문 안했으니까 방문 처리
        visited[v] = true;
        //노드 v와 연결된 모든 노드 중 방문 안한거면
        for(int i: nums[v]) {
            if(!visited[i]) {
                DFS(i);
            }

    }

    }
}