[백준 - 11724] 연결요소의 개수 (bfs) - java

[백준 - 11724] 연결요소의 개수 (bfs) - java

---

문제 설명

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

 

입력

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

 

출력

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

 

 

풀이

일반적인 bfs 문제와는 약간 다른? 느낌의 문제였다.

사실 bfs, dfs 알고리즘 모두 그래프지만

내가 느낀 알고리즘 문제에서의 bfs, dfs는 2차원 배열과 다르지 않았다.

그래서 오랜만에 그래프의 개념을 다시 정리하며 문제를 풀이했다.

먼저 그래프에서 연결요소라는 개념을 다시 찾아봤다.

연결요소란 그래프에서 연결된 그래프들을 말한다.

 

구현을 위해 인접행렬 & 인접 배열을 사용하여 표현할 수 있다.

나는 인접 배열을 이용하고 ArrayList안에 ArrayList가 들어있는 형태로 구현했다.

 

인접배열에 정점 u와 정점 v 를 양방향으로 연결시킨다.

visited배열을 돌면서 방문하지 않은 정점이 있다면 bfs 탐색을 시작하여

연결된 정점들을 탐색하며 visited배열에 방문 표시를 해주었다.

 

이렇게 방문하지 않은 정점을 탐색하며 count값을 ++하여 출력했다.

 

어려운 문제는 아니였지만 일반적인 2차원 배열을 상하좌우로 탐색하는

알고리즘 문제와는 다르게 그래프의 정점을 직접 이어주고 탐색하는 문제는

이번이 처음이라 그래프의 개념이 조금 부족했다.

 

코드

package baekJoon.BFS;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
// 연결요소
public class B_11724 {
    static ArrayList<ArrayList<Integer>> list;
    static boolean[] visited;
    private static void solution () {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
 
        visited = new boolean[N+1];
        list = new ArrayList<ArrayList<Integer>>();
 
        for(int i=0; i<N+1; i++) {
            list.add(new ArrayList<Integer>());
        }
 
        for(int i=0; i<M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
 
            list.get(u).add(v);
            list.get(v).add(u);
        }
        int count = 0;
        for(int i=1; i<N+1; i++) {
            if(!visited[i]) {
                bfs(i);
                count++;
            }
        }
        System.out.println(count);
    }
 
 
    private static void bfs (int n) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(n);
 
        while(!queue.isEmpty()) {
            int data = queue.poll();
            visited[data] = true;
 
            for(int i=0; i< list.get(data).size(); i++) {
                int result = list.get(data).get(i);
                if(!visited[result]) {
                    visited[result] = true;
                    queue.add(result);
                }
            }
        }
    }
 
    public static void main(String[] args) {
        solution();
    }
}