백준 11724 : 연결 요소의 개수 (그래프 탐색)

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1 복사

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1 복사

2

예제 입력 2 복사

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2 복사

1

 

• 풀이

무방향 그래프를 탐색할때 연결된 묶음? 이 몇개 나오는지 물어보는 문제라

dfs든 bfs든 호출될때마다 연결된 그래프는 다 도니까 아직 방문하지 않은 정점부터 시작하는 dfs나 bfs를 solution 함수에서 호출하고 solution 함수에서 호출한 횟수를 리턴하면 됐다

하는김에 dfs, bfs 둘다 연습할겸 해봤다

 

dfs, 인접 행렬로 풀이

import java.io.*;
import java.sql.Array;
import java.util.*;

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

    static void dfs(int x){
        visited[x] = true;

        for (int i = 1; i <= N; i++){
            if (arr[x][i] == 0) continue;
            if (visited[i]) continue;
            dfs(i);
        }
    }

    static void solution(){
        for (int i = 1; i <= N; i++){
            if (!visited[i]){
                res++;
                dfs(i);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner in =new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        arr = new int[N+1][N+1];
        visited = new boolean[N+1];
        for (int i = 1; i <= M; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            arr[a][b] = 1;
            arr[b][a] = 1;
        }
        solution();
        System.out.println(res);
    }
}

 

dfs, 인접 리스트 풀이

 

public class Main {
    static int N, M;
    static int res = 0;
    static ArrayList<Integer>[] arr;
    static boolean[] visited;

    static void solution(){
        for (int i =1; i <= N; i++){
            if (!visited[i]){
                res++;
                dfs(i);
            }
        }
    }

    static void dfs(int x){
        visited[x] = true;
        for (int y : arr[x]){
            if (visited[y]) continue;
            dfs(y);
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner in =new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();

        arr = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) arr[i] = new ArrayList<>();
        visited = new boolean[N+1];
        for (int i = 1; i <= M; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            arr[a].add(b);
            arr[b].add(a);
        }
        solution();
        System.out.println(res);
    }
}

 

bfs, 인접 행렬 풀이

import java.io.*;
import java.sql.Array;
import java.util.*;

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

    static void solution(){
        for (int i = 1; i <= N; i++){
            if (!visited[i]) {
                bfs(i);
                res++;
            }
        }
    }
    static void bfs(int x){
        Queue<Integer> que = new LinkedList<>();
        que.add(x);
        visited[x] = true;
        while (!que.isEmpty()){
            int tmp = que.poll();
            for (int i = 1; i <= N; i++){
                if (visited[i]) continue;
                if (arr[tmp][i] != 1) continue;
                que.add(i);
                visited[i] = true;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner in =new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();

        arr = new int[N+1][N+1];
        visited = new boolean[N+1];
        for (int i = 1; i <= M; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            arr[a][b] = 1;
            arr[b][a] = 1;
        }
        solution();
        System.out.println(res);
    }
}

 

bfs 인접 리스트 풀이

import java.io.*;
import java.sql.Array;
import java.util.*;

public class Main {
    static int N, M;
    static int res = 0;
    static ArrayList<Integer>[] arr;
    static boolean[] visited;

    static void solution(){
        for (int i = 1; i <= N; i++){
            if (!visited[i]) {
                bfs(i);
                res++;
            }
        }
    }
    static void bfs(int x){
        Queue<Integer> que = new LinkedList<>();
        que.add(x);
        visited[x] = true;
        while (!que.isEmpty()){
            int tmp = que.poll();
            for (int y : arr[tmp]){
                if (visited[y]) continue;
                que.add(y);
                visited[y] = true;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner in =new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();

        arr = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) arr[i] = new ArrayList<>();
        visited = new boolean[N+1];
        for (int i = 1; i <= M; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            arr[a].add(b);
            arr[b].add(a);
        }
        solution();
        System.out.println(res);
    }
}