2022-09-13 algorithm

boj_11724 연결 요소의 개수 - silver 2

Link : 연결 요소의 개수

정보

문제

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

입력

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

출력

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

예제 입력1

예제 출력1

풀이

1. 방문을 체크해줄 visited와 간선의 그래프를 나타내주는 graph를 선언한다.
2. 첫번째 정점부터 방문하면서 이어진 정점으로 가면서 정점을 방문한다.
3. 끊어지면 정점이 안 이어진것이므로 개수를 세준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n,m;
    static boolean[] visited;
    static int[][] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        // 계산을 편하게 해주기 위해 +1해서 선언
        visited = new boolean[n+1];
        graph = new int[n+1][n+1];

        // 그래프 간선 이어주기
        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");
            int u = Integer.parseInt(input[0]);
            int v = Integer.parseInt(input[1]);
            graph[u][v] = 1;
            graph[v][u] = 1;
        }
        
        // 정답 개수를 세기위한 answer 선언 후 0으로 초기화
        int answer = 0;
        
        // 정점을 돌면서 방문하지 않으면 방문하고 이어진 정점 다 돌면 answer증가
        for (int i = 1; i <= n; i++) {
            if(!visited[i]){
                dfs(i);
                answer++;
            }
        }
        System.out.println(answer);
    }
    
    static void dfs(int point){
        visited[point] = true;
        for (int i = 1; i <= n; i++) {
            if(!visited[i] && graph[point][i]==1){
                dfs(i);
            }
        }
    }
}

결과

tags: algorithm, Boj, dfs