[Baekjoon] 11724 연결 요소의 개수 - JAVA

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (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

---

📝 제출 답안

✔️ BFS 탐색

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] link;
    static boolean[] visited;
    static int n, m;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

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

        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                BFS(i);
                count++;
            }
        }

        System.out.println(count);
    }

    public static void BFS(int st) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(st);
        visited[st] = true;

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

            for (int i = 1; i <= n; i++) {
                if (link[node][i] == 1 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

 

 

✔️ DFS 탐색

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] link;
    static boolean[] visited;
    static int n, m;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

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

        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                DFS(i);
                count++;
            }
        }

        System.out.println(count);
    }

    public static void DFS(int node) {
        visited[node] = true;

        for (int i = 1; i <= n; i++) {
            if (link[node][i] == 1 && !visited[i]) {
                DFS(i);
            }
        }
    }
}

 

 

입력 및 초기화

BufferedReader로 빠른 입력 처리를 하고, StringTokenizer를 통해 한 줄에 공백을 기준으로 여러 개의 입력을 처리하도록 해줬다.

정점 간 연결 여부를 인접 행렬 link[][]을 통해 표현해주고,

각 정점의 방문 여부를 저장할 1차원 배열 visited[] 선언해주었다.

n,m 은 각각 정점과 간선 개수를 입력받기 위한 변수이다.

 

정점 개수 n과 간선 개수 m을 입력 받은 후 link와 visited의 크기를 n+1로 초기화해준다.

간선 개수 만큼 반복하면서 두 정점의 연결 여부를 1로 설정한다. 이때 무방향 그래프이므로 대칭으로 저장해준다.

인접행렬은 link[i][j] == 1이면 i와 j가 연결된 것으로 볼 수 있다.

st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());

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

 

 

연결 요소 개수 구하기

연결 요소의 총 개수를 카운트할 변수 count를 0으로 초기화해준다.

 

for문을 통해 1번 노드부터 n번 노드까지 확인하면서

아직 방문하지 않은 노드가 있다면 BFS 또는 DFS 탐색을 수행한다.

각 탐색이 끝날 때마다 새로운 연결 요소를 발견하는 것이므로 count++를 실행한다.

 

최종적으로는 연결 요소 개수를 모두 합한 count를 출력해준다.

int count = 0;
for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        BFS(i); DFS(i);	// DFS 또는 BFS 탐색 사용
        count++;
    }
}
System.out.println(count);

 

---

 

🪄 BFS 코드 풀이

BFS는 Queue 자료 구조를 사용해 탐색을 수행하므로 가장 먼저 Queue를 선언해준다.

 

탐색을 시작한 노드 번호를 큐에 넣고 → queue.add(st);

방문 표시를 한다. →  visited[st] = true;

 

다음으로 큐가 빌 때까지 while문을 반복한다.

현재 노드를 꺼내고 for문을 통해 1부터 n까지 현재 노드와 연결된 모든 노드를 확인한다.

연결된 노드 중 방문하지 않은 노드가 있으면 노드를 큐에 추가한다.

 

현재 BFS 코드는 인접 행렬을 사용해 총 시간 복잡도는 O(N^2)이다.

해당 문제에서는 인접 행렬보다 인접 리스트를 사용하면 빠른 탐색과 메모리 절약, 연결된 노드만 탐색해 불필요한 연산을 제거할 수 있다는 장점이 있다. 인접 리스트 사용 시 시간 복잡도를 O(N+M)으로 줄일 수 있다.

(인접리스트로 풀 생각을 못해서 구글링해보다가 알게됨.)

public static void BFS(int st) {
    Queue<Integer> queue = new LinkedList<>();

    queue.add(st);
    visited[st] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();  // 현재 노드 꺼내기

        for (int i = 1; i <= n; i++) { // 모든 노드 확인
            if (link[node][i] == 1 && !visited[i]) { // 연결되어 있고 방문 안 한 경우
                queue.add(i);  // 큐에 추가
                visited[i] = true; // 방문 처리
            }
        }
    }
}

 

---

 

🪄DFS 코드 풀이

DFS는 BFS와 달리 Queue를 사용하지 않고 재귀를 사용해 해결한다.

 

DFS는 호출과 동시에 현재 방문한 노드를 방문 처리해준다.

 

for문을 통해 1번부터 n번째 노드를 순회하면서 현재 노드와 연결되었는데 아직 방문하지 않은 노드를 재귀 호출을 통해 탐색을 계속한다.

public static void DFS(int node) {
    visited[node] = true;

    for (int i = 1; i <= n; i++) {
        if (link[node][i] == 1 && !visited[i]) {
            DFS(i);
        }
    }
}

 

---

 

⚡DFS vs. BFS

DFS는 연결 요소 탐색에 적합하고, BFS는 최단 거리 탐색에 적합하다.

그러므로 해당 문제에서는 한 방향으로 끝까지 탐색하는 방식으로 연결 요소를 찾기에 적합한 DFS를 사요하는 것이 더 적절할 것 같다. BFS와 비교하면 메모리를 덜 사용하지만, 깊이가 깊은 경우에는 효율성이 떨어질 수 있다.

 

 

제출 현황(위 DFS, 아래 BFS)