[알고리즘-JAVA] 백준 알고리즘 11724번 - 연결 요소의 개수

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

그래프 연결 요소의 개수를 구하는 문제이다.

2. 나의 방식대로 문제를 재정의 하자.

각 연결요소별로 dfs나 bfs를 돌려서 전부 탐색하게 한 뒤에,

총 연결요소의 개수를 구해내면 되는 문제이다.

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

dfs, ArrayList

4. 어떻게 계산할 것인가?
1) 입력

BufferedReader, InputStreamReader를 이용

 

2) 시간 복잡도 계산

O(N)

5. 주의할 점은 무엇인가?

연결 요소의 개수를 구하는 문제이기 때문에,

check[]가 false인 모든 구간에서 dfs를 한번씩 다 해줘야 한다.

 

6. 풀이 과정

dfs/bfs 둘다 사용해서 풀이가 가능한데, 나는 dfs/ bfs를 모두 구현해봤다.

dfs/bfs는 인접행렬과, 인접 리스트를 통해 구현할 수 있는데

나는 인접 행렬이 쓸모없는 메모리를 많이 사용하기 때문에

인접 리스트로 구현을 했다.

인접리스트를 위해 ArrayList안에 ArrayList를 넣은 2중 배열을 사용했고

check[]배열을 통해서 해당 노드에 갔는지 안갔는지를 판별했다.

 

만약 해당 노드에 갔으면 -> check[node] = true이고

가지 않았으면 -> check[node] = false이다.

 

[전체 소스 코드]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    public static ArrayList<ArrayList<Integer>> array;
    public static boolean check[];
    public static Queue<Integer> q;
    public static int linkcount;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(stk.nextToken());
        int m = Integer.parseInt(stk.nextToken());

        check = new boolean[n + 1];
        linkcount = 0;

        array = new ArrayList<ArrayList<Integer>>();
        // 입력받은 정점 + 1개로 인덱스 1부터 시작.
        for (int i = 0; i < n + 1; i++) {
            array.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(stk.nextToken());
            int v = Integer.parseInt(stk.nextToken());

            array.get(u).add(v);
            array.get(v).add(u);
        }

        for (int i = 1; i <= n; i++) {
            if (check[i] == false) {
                //dfs(i);
                bfs(i);
                linkcount += 1;
            }
        }
        // printGraphToAdjList();
        System.out.println(linkcount);
    }

    // 그래프 출력 (인접리스트)
    public static void printGraphToAdjList() {
        for (int i = 1; i < array.size(); i++) {
            System.out.print("정점 " + i + "의 인접리스트");

            for (int j = 0; j < array.get(i).size(); j++) {
                System.out.print(" -> " + array.get(i).get(j));
            }
            System.out.println();
        }
    }

    public static void dfs(int n) {
        check[n] = true;
        for (int i = 0; i < array.get(n).size(); i++) {
            int next = array.get(n).get(i);
            if (check[next] == false) {
                dfs(next);
            }
        }
    }

    public static void bfs(int n){
        q = new LinkedList<Integer>();
        check[n] = true;
        q.offer(n);
        while (!q.isEmpty()){
            int x = q.poll();
            for (int i = 0; i < array.get(x).size(); i++){
                int y = array.get(x).get(i);
                if (check[y] == false){
                    check[y] = true;
                    q.offer(y);
                }
            }
        }
    }
}