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

3초

512 MB

문제

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

입력

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

출력

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

 

---

<생각의 흐름>

제한시간 3초, N은 최대 1000 -> O(n^2) 알고리즘 사용해도 될 듯
연결 요소는 에지로 연결된 노드의 집합이며, 한번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단할 수 있음
즉 DFS로 돌면서 방문배열에 대해서 true로 바꾸고 끝까지 돌면 될듯??

우선 인접리스트로 그래프를 구현해보자 + 방문 배열도 필요
DFS의 수행횟수가 연결 요소 갯수이다.

 

<코드>

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; // 가중치 있을 때는 <Node>
    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());

        visited = new boolean[n+1]; // 0번 인덱스는 안씀
        A = new ArrayList[n+1];
        for(int i = 1; i < n+1 ; i++){
            A[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()); // 종료점

            A[s].add(e); // 방향없을 때는 양쪽다 해줘야함 (중요!)
            A[e].add(s);
        }

        int count = 0;
        for(int i = 1; i < n+1 ; i++) {
            if(!visited[i]){ // 방문안한곳이면
                count++;
                DFS(i);
            }
        }
        System.out.println(count);
    }

    private static void DFS(int v) { // 재귀
        if(visited[v]){
            return;
        }
        visited[v] = true;
        for(int i : A[v]){
            if(!visited[i]){
                DFS(i);
            }
        }
    }
}

---

<피드백>

 

우선 static 변수로 방문 배열과 그래프를 표현할 인접리스트를 선언한다.

static boolean visited[];
static ArrayList<Integer>[] A; // 가중치 있을 때는 <Node>

 

ArrayList 배열의 원소 하나당 또 ArrayList를 넣어줘야함

visited = new boolean[n+1]; // 0번 인덱스는 안씀
A = new ArrayList[n+1];
for(int i = 1; i < n+1 ; i++){
    A[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()); // 종료점

    A[s].add(e); // 방향없을 때는 양쪽다 해줘야함 (중요!)
    A[e].add(s);
}

 

DFS 메서드 구현

private static void DFS(int v) { // 재귀
    if(visited[v]){
        return;
    }
    visited[v] = true;
    for(int i : A[v]){
        if(!visited[i]){
            DFS(i);
        }
    }
}