[JAVA] 백준 11724번: 연결 요소의 개수

 

---

문제

• 방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 문제.

 

아이디어

• 그래프를 입력 받고, DFS 혹은 BFS를 통해 노드를 탐색하며 연결 가지 수를 체크한다.
• 그래프를 구현하기 위해 2차원 boolean 배열을 선언한 후, 간선을 연결한다.
  • 한 노드를 지정해 visited 배열로 연결된 모든 노드를 탐색한 후(가지 하나를 모두 탐색) 카운트를 한다.
  • 이 과정을 반복한다.

 

풀이(BFS)

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

public class Main {
    static int N, M;
    // 그래프 입력을 위한 배열들 선언
    static boolean[][] graph;
    static boolean[] visited;
    // bfs에서 사용하기 위한 큐 선언
    static Deque<Integer> queue;
    public static void main(String[] args) 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());
        graph = new boolean[N][N];
        visited = new boolean[N];
        queue = new ArrayDeque<>();
        
        // 그래프 입력
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken())-1;
            int n2 = Integer.parseInt(st.nextToken())-1;
            graph[n1][n2] = true;
            graph[n2][n1] = true;
        }

        int answer = 0;
        
        // 각 노드를 탐색하며 연결된 요소를 모두 탐색
        // 탐색이 끝나면 한 가지가 모두 탐색된 의미이므로 answer + 1
        for(int i=0; i<N; i++) {
            if(!visited[i]) {
                visited[i] = true;
                queue.addLast(i);
                bfs();
                answer++;
            }
        }
        System.out.println(answer);
    }
    static void bfs() {
        while(!queue.isEmpty()) {
            int node = queue.removeFirst();
            for(int i=0; i<N; i++) {
                if(graph[node][i] && !visited[i]) {
                    queue.addLast(i);
                    visited[i] = true;
                }
            }
        }
    }
}

 

풀이(DFS)

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

public class Main {
    static int N, M;
    // 그래프 탐색을 위한 배열들 선언
    static boolean[][] graph;
    static boolean[] visited;
    public static void main(String[] args) 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());
        graph = new boolean[N][N];
        visited = new boolean[N];
        
        // 그래프 입력
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken())-1;
            int n2 = Integer.parseInt(st.nextToken())-1;
            graph[n1][n2] = true;
            graph[n2][n1] = true;
        }

        int answer = 0;
        for(int i=0; i<N; i++) {
            if(!visited[i]) {
                dfs(i);
                answer++;
            }
        }
        System.out.println(answer);
    }
    static void dfs(int node) {
        visited[node] = true;
        for(int i=0; i<N; i++) {
            if(graph[node][i] && !visited[i]) {
                dfs(i);
            }
        }
    }
}

 

채점 결과

BFS 풀이(위), DFS 풀이(아래)

기타

• DFS와 BFS 풀이 간 유의미한 시간 및 메모리 차이는 없었다.

 

문제 링크

• 11724번: 연결 요소의 개수 (acmicpc.net)