[BOJ 11724] 연결 요소의 개수 (Java, 그래프 탐색)

 

---

문제 링크 

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

11724번: 연결 요소의 개수

---

풀이 

- 전형적인 그래프 탐색 문제

- 방향없는 그래프 키워드에서 양방향 그래프라 생각하고 인접 리스트에 정점, 간선 데이터 입력

- 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)

- 최대 N = 1,000, M = 1000*999/2 = 499500 일 때 그래프 탐색하게 될 경우 O(4995 * 10^5) 시간복잡도 가짐

- 약 5억 이하라서 Integer 처리 가능

- 방문 배열을 사용하여 그룹 카운팅 수행

---

제출 코드

 

bfs, dfs 둘 다 정의

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

public class Main {
    static int N, M;

    static List<Integer>[] adj;

    static boolean[] visit;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 정점의 개수
        M = Integer.parseInt(st.nextToken()); // 간선의 개수

        visit = new boolean[N + 1];
        adj = new ArrayList[N + 1];
        for(int i = 0; i <= N; i++) adj[i] = new ArrayList();

        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            adj[from].add(to);
            adj[to].add(from);
        }

        for(int i = 1; i <= N; i++) Collections.sort(adj[i]);
    }

    static void dfs(int x) {
        visit[x] = true;

        for(int y : adj[x]) {
            if(visit[y]) continue;

            dfs(y);
        }
    }

    static void bfs(int x) {
        Queue<Integer> que = new LinkedList<>();
        que.add(x);
        visit[x] = true;

        while(!que.isEmpty()) {
            int i = que.poll();

            for(int j : adj[i]) {
                if(visit[j]) continue;

                visit[j] = true;
                que.add(j);
            }
        }
    }

    static void pro() {
        int cnt = 0;
        for(int i = 1; i <= N; i++) {
            if(!visit[i]) {
                cnt += 1;
                //dfs(i);
                bfs(i);
            }
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}