[DFS/BFS] 백준 11724번 연결 요소의 개수(Java)

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

11724번: 연결 요소의 개수

📚 문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. 같은 간선은 한 번만 주어진다.

예제 입력	예제 출력
6 5 1 2 2 5 5 1 3 4 4 6	2
6 8 1 2 2 5 5 1 3 4 4 6 5 4 2 4 2 3	1

 

📝 문제 해결

i번에 연결된 모든 요소는 이미 방문 처리되므로 탐색 후 카운트 +1 -> 아직 방문하지않은 노드들에 대해 반복적으로 메서드를 호출해 모든 노드 탐색

 

💻 코드

• DFS (깊이 우선 탐색)

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

public class Main{
    static int N, M;
    static int[][] graph;
    static boolean[] visited;
    
    static void dfs(int index){
        visited[index] = true;
        
        for(int i=1; i<=N; i++){
            if(graph[index][i]==1 && !visited[i]) dfs(i);
        }
    }
    
    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 a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a][b] = graph[b][a] = 1;
        }
        
        int count = 0;
        for(int i=1; i<=N; i++){
            if(!visited[i]){
				dfs(i);
				count++;
            }
        }
        
        System.out.println(count);
    }
}

 

• BFS (너비 우선 탐색)

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

public class Main{
    static int N, M;
    static int[][] graph;
    static boolean[] visited;
    
    static void bfs(int index){
        Queue<Integer> que = new LinkedList<>();
        visited[index] = true;
        que.offer(index);
        
        while(!que.isEmpty()){
            int temp = que.poll();
            
            for(int i=1; i<=N; i++){
                if(graph[temp][i]==1 && !visited[i]){
                    que.offer(i);
                    visited[i] = true;
                }
            }
        }
    }
    
    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 a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a][b] = graph[b][a] = 1;
        }
        
        int count = 0;
        for(int i=1; i<=N; i++){
           if(!visited[i]) {
			bfs(i);
			count++;
			}
		}
        
        System.out.println(count);
    }
}