알고리즘 풀이 - 백준 11724(연결 요소의 개수, 그래프(DFS, BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

그래프 구조에서 연결 요소의 개수를 구하는 문제

 

2. 풀이

 

연결 요소란 그래프 상에서 이어져 있는 모든 정점들이 있을 때, 그것을 하나의 연결 요소라고 한다. 예를 들어 아래의 그림을 보자.

위 그래프에서 1, 2, 4는 하나의 연결된 그래프이므로 1개의 연결 요소 이고 3, 5도 하나의 연결된 그래프라서 1개의 연결 요소 이다.

즉, 위 그림에서 연결 요소의 개수는 2개가 되는 것이다.

 

따라서, DFS, BFS로 2가지 중 1가지의 방법을 사용하여 그래프 탐색을 시도한 뒤 연결 요소의 개수를 구하는 코드를 구현하면 해결할 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① DFS로 구현

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

public class Main{
    static int n;
    static int m;
    static ArrayList<Integer> graph[];
    static boolean[] visited;
    static int ans = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n+1];
        visited = new boolean[n+1];
        for(int i=1; i <= n; i++){
            graph[i] = new ArrayList<>();
        }

        // 양방향 연결 그래프로 생성
        for(int i=0; i < m; i++){
            st = new StringTokenizer(br.readLine());

            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph[u].add(v);
            graph[v].add(u);
        }

        // 끊어진 부분이 있을 수 있으니 모든 부분에서 탐색 시작
        // 탐색을 시작할 정점은 이미 이전에 방문이 되지 않았어야 함
        for(int i=1; i <= n; i++){
            if(!visited[i]){
                dfs(i);
                
                // 탐색을 수행할 때마다 연결요소 ++
                ans++;
            }

        }
        bw.write(String.valueOf(ans));
        bw.flush();
        br.close();
    }

    // DFS를 수행. 인접 정점은 모두 방문 완료 처리를 한다.
    private static void dfs(int curr){
        for(int next : graph[curr]){
            if(!visited[next]){
                visited[next] = true;
                dfs(next);
            }
        }
    }
}

 

 

② BFS로 구현

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

public class Main{
    static int n;
    static int m;
    static ArrayList<Integer> graph[];
    static boolean[] visited;
    static int ans = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n+1];
        visited = new boolean[n+1];
        for(int i=1; i <= n; i++){
            graph[i] = new ArrayList<>();
        }

        // 양방향 연결 그래프로 생성
        for(int i=0; i < m; i++){
            st = new StringTokenizer(br.readLine());

            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph[u].add(v);
            graph[v].add(u);
        }

        // 끊어진 부분이 있을 수 있으니 모든 부분에서 탐색 시작
        // 탐색을 시작할 정점은 이미 이전에 방문이 되지 않았어야 함
        for(int i=1; i <= n; i++){
            if(!visited[i]){
                bfs(i);

                // 탐색을 수행할 때마다 연결요소 ++
                ans++;
            }

        }
        bw.write(String.valueOf(ans));
        bw.flush();
        br.close();
    }

    // BFS를 수행. 인접 정점은 모두 방문 완료 처리를 한다.
    private static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = true;

        while(!q.isEmpty()){
            int curr = q.poll();

            for(int next : graph[curr]){
                if(!visited[next]){
                    q.offer(next);
                    visited[next] = true;
                }
            }
        }
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.