BOJ 11724

2020-05-29

위 문제는 백준 사이트의 알고리즘 11724 문제에 관한 설명입니다.

문제

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

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.

(1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다.

(1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

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

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class ConnectionThing {
    static int n;
    static int m;
    static int[][] map;
    static boolean[] visited;
    static int result = 0;
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        n = scanner.nextInt();
        m = scanner.nextInt();
        
        map = new int[n][n];//맵
        visited = new boolean[n];//방문했는가
        
        for(int i=0; i<m; i++) {
            int a = scanner.nextInt();//시작점
            int b = scanner.nextInt();//끝점
            
            map[a-1][b-1] = 1;//연결되어있다는 상태
            map[b-1][a-1] = 1;//그 반대의 경우 (1, 2번이 연결되있다는건 2, 1번도 연결되어있다와 같은상태)
        }
        
        for(int i=0; i<n; i++) {
            if(!visited[i]) {
                bfs(i);
                result++;
            }
        }
        
        System.out.println(result);
        
    }
    
    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(start);//시작점은 start(int로 넘어온 값)
        visited[start] = true;//시작점부터 시작하기에 방문했다고 설정
        
        while(!queue.isEmpty()) {
            int v = queue.poll();//하나 꺼내옴
            
            for(int i=0; i<n; i++) {
                if(map[v][i] == 1 && !visited[i]) {//연결되어있고 방문한 적이 없다면?
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

해당 문제 예시1번을 기준으로 설명하자면

정점, 간선의 갯수를 입력받고

125의 연결간선, 346의 연결간선으로 2덩이가 나와서 값이 2가 나타납니다.

1부터 N까지 DFS또는 BFS를 돌려서 끝나는 시점에 카운트를 하나 증가시켜 주면

다음 시작 요소로 DFS를 돌리는 식으로 반복하면 답을 구할 수 있다.

연결 요소의