백준 11724 ( Java )

 

안녕하세요 besforyou입니다.

백준 11724 문제풀이를 적어보겠습니다.

 

---

문제 해설

 

정점과 간선이 주어졌을 때 방향 없는 그래프의 연결 요소( Connected Component )의 개수를 구하는 문제입니다.

 

---

문제 풀이

 

Connected Component의 개수는 dfs로 쉽게 알 수 있습니다.

 

dfs로 방향 없는 그래프를 탐색하면 한번 탐색할 때 연결된 모든 정점들을 한 번씩 탐색합니다.

 

그러므로 dfs함수를 호출한 횟수가 connected component의 개수입니다.

 

---

코드

import java.util.Scanner;
 
public class Main {
 
    static int N,M;
    static int graph[][];
    static boolean visited[];
 
    public static void main(String []args) {
 
        Scanner sc = new Scanner(System.in);
 
        N = sc.nextInt();
        M = sc.nextInt();
 
        graph = new int[N+1][N+1];
        visited = new boolean[N+1];
 
        int one, two;
        for ( int i = 0 ; i < M ; i++ ) {
            one = sc.nextInt();
            two = sc.nextInt();
 
            graph[one][two] = graph[two][one] = 1;
        }
 
        int count = 0;
 
        for ( int i = 1 ; i <= N ; i++ ) {
            if ( visited[i] == false ) {
                dfs(i);
                count++;
            }
        }
 
        System.out.println(count);
 
        return ;
    }
 
    public static void dfs(int k) {
        if ( visited[k] == true )
            return;
 
        visited[k] = true;
 
        for ( int i = 1 ; i <= N ; i++ ) {
            if ( graph[k][i] == 1 ) {
                dfs(i);
            }
        }
    }
}
 

---

결과

 

자바는 확실히 느리네요