[BOJ] 11724 - 연결 요소의 개수(Java)

문제 설명

https://www.acmicpc.net/problem/11724

 

---

🔍 접근법

이 문제는 서로 연결된 정점들을 하나의 묶음(연결 요소)으로 보고, 그런 묶음이 총 몇 개인지를 세는 전형적인 그래프 탐색 문제입니다. 한 정점을 기준으로 더 이상 연결된 노드가 없을 때까지 탐색을 반복하면 해당 연결 요소 전체를 방문하게 되므로, 그래프 전체를 순회하면서 아직 방문하지 않은 정점이 발견될 때마다 DFS 또는 BFS 탐색을 시작하면 됩니다. DFS, BFS 모두 적용 가능하다고 판단하여 DFS로 먼저 풀어본 뒤, 동일한 방식으로 BFS도 구현해 보았습니다. 구현 과정에서 유의할 점은, 인접 행렬 기반 DFS에서 graph[x][y]가 1인 경우 y를 다음 탐색 대상 노드로 삼는다는 구조이며, 이는 다음 DFS 호출의 인자값으로 y가 들어가는 흐름이라는 점에서 명확히 이해하고 넘어갈 필요가 있습니다.

---

💻 코드

• dfs

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

public class Main {
    static int N, M;
    static int[][] graph;
    static boolean[] visited;
    static int count=0;

    public static void main(String[] args) throws IOException{
        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 int[N+1][N+1];
        visited = new boolean[N+1];

        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][v] = 1;
            graph[v][u] = 1;
        }

        for(int i=1; i<N+1; i++){
            if(!visited[i]){ //방문하지않았으면 dfs 시작
                dfs(i);
                count++; //dfs 끝나면 연결요소 개수 +1
            }
        }

        System.out.println(count);
    }

    public static void dfs(int x){
        visited[x] = true; //현재 노드 방문 처리

        for(int i=1; i<=N; i++){
            if(graph[x][i] == 1 && !visited[i]){ //값이 존재하며 아직 방문하지 않았으면 dfs 시작
                dfs(i);
            }
        }
    }
}

• bfs

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

public class Main {
    static int N, M;
    static int[][] graph;
    static boolean[] visited;
    static int count=0;

    public static void main(String[] args) throws IOException{
        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 int[N+1][N+1];
        visited = new boolean[N+1];

        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][v] = 1;
            graph[v][u] = 1;
        }

        for(int i=1; i<N+1; i++){
            if(!visited[i]){ //방문하지않았으면 dfs 시작
                bfs(i);
                count++; //dfs 끝나면 연결요소 개수 +1
            }
        }

        System.out.println(count);
    }

    public static void bfs(int x){
        visited[x] = true;
        Queue<Integer> q = new LinkedList<>();
        q.offer(x);

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

            for(int i=1; i<=N; i++){
                if(!visited[i] && graph[node][i] == 1){ //i는 가야할 곳, node는 현재 위치
                    visited[i] = true;
                    q.offer(i);
                }
            }
        }
    }
}

---

💡 정리 및 느낀 점

• dfs, bfs 둘다 사용해서 계속 풀어보는 연습하기!!

---