[백준 11724] 연결 요소의 개수 (C++/Java)

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
vector<int> arr[1002];
queue<int> q;
bool check[1002];
int n,m,u,v,ans;
void dfs(int node) {
    check[node]=true;
    
    for(int i=0; i<arr[node].size(); i++) {
        int next=arr[node][i];
        if(!check[next])
            dfs(next);
    }
}
void bfs(int start) {
    check[start]=true; q.push(start);
    
    while(!q.empty()) {
        int node=q.front(); q.pop();
        
        for(int i=0; i<arr[node].size(); i++){
            int next=arr[node][i];
            
            if(!check[next]) {
                q.push(next);
                check[next]=true;
            }
        }
    }
}
int main(void) {
    scanf("%d %d", &n, &m);
    for(int i=0; i<m; i++) {
        scanf("%d %d", &u, &v);
        arr[u].push_back(v);
        arr[v].push_back(u);
    }
    
    for(int i=1; i<=n; i++) {
        if(!check[i]) {
//            dfs(i);
            bfs(i);
            ans++;
        }
    }
    printf("%d", ans);
    
    return 0;
}

 

DFS와 BFS 문제 코드 그대로 가져다 사용하면 된다.

주의할 점은 정점이 모두 연결되어 있을 것이란 보장은 없기 때문에 모든 점들에 대해 방문여부를 확인해줘야한다.

 

 

- 자바

1. 2차원 배열 + BFS

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
 
public class Main{
    static Queue<Integer> q = new LinkedList<>();
    static int[][] arr;
    static boolean[] visited;
    static int n=0, m=0;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st;
 
        // n,m 입력받고 크기에 맞는 2차원 배열과 boolean 배열 만들기
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n+1][n+1];
        visited = new boolean[n+1];
 
        // 간선 입력받기
        int u=0, v=0;
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine(), " ");
            
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            arr[u][v] = 1;
            arr[v][u] = 1;
        }
 
        // bfs 돌리기
        int ans=0;
        for(int i=1; i<=n; i++){
            if(visited[i] == false){
                ans++;
                bfs(i);
            }
        }
 
        System.out.println(ans);
    }
 
    public static void bfs(int start){
        visited[start] = true;
        q.add(start);
 
        while(!q.isEmpty()){
            int front = q.peek(); q.remove();
            
            for(int i=1; i<=n; i++){
                if(arr[front][i] == 1 && visited[i] == false){
                    visited[i] = true;
                    q.add(i);
                }
            }
        }
    }
}

 

 

2. 리스트 + DFS

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Queue;
 
public class Main{
    static ArrayList<Integer> arr[];
    static boolean[] visited;
    static StringBuilder sb;
    static int n, m;
    static Queue<Integer> q = new LinkedList<Integer>();
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        // n과 m 입력받기
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        visited = new boolean[n+1];
        arr = new ArrayList[n+1];
        
        for(int i=0; i<=n; i++){
            arr[i] = new ArrayList<Integer>();
        }
 
        // 간선 입력받기
        int u=0, v=0;
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine(), " ");
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            arr[u].add(v);
            arr[v].add(u);
        }
 
        // 연결요소 개수 
        int ans=0;
        for(int i=1; i<=n; i++){
            if(visited[i] == false){
                dfs(i);
                ans++;
            }
        }
        System.out.println(ans);
        
        return;
    }
 
    public static void dfs(int node){
        visited[node] = true;
        
        for(int next : arr[node]){
            if(visited[next]==false){
                dfs(next);
            }
        }
    }
}