[Java] baekjoon_11724 : 연결 요소의 개수

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

연결 요소의 개수 : Silver2

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

11724번: 연결 요소의 개수

 

 

DFS(Depth-First Search) 알고리즘을 사용하여 방향 없는 그래프의 연결 요소(Connected Component) 개수를 찾도록 했다.

 

 

풀이

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

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
  static ArrayList<ArrayList<Integer>> graph;
  static boolean[] visited;

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

    // 그래프 초기화
    graph = new ArrayList<>();
    visited = new boolean[N + 1];
    for (int i = 0; i <= N; i++) {
      graph.add(new ArrayList<>());
    }

    // 간선 정보 입력
    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.get(u).add(v);
      graph.get(v).add(u);
    }

    int cnt = 0; // 연결 요소 개수 카운트
    for (int i = 1; i <= N; i++) {
      if (!visited[i]) {
        dfs(i);
        cnt++;
      }
    }

    bw.write(cnt + "\n");
    bw.flush();
    br.close();
    bw.close();
  }
  
  static void dfs(int node) {
    visited[node] = true;
    for (int next : graph.get(node)) {
      if (!visited[next]) {
        dfs(next);
      }
    }
  }
}

 

 

graph와 visited 배열 초기화

graph : ArrayList를 이용하여 각 정점마다 연결된 정점들을 저장하는 그래프를 만든다.

visited : 각 정점의 방문 여부를 나타내는 boolean 배열이다.

 

간선 정보 입력

입력으로 주어지는 간선 정보를 바탕으로 그래프를 구성한다.

방향 없는 그래프이므로 양방향으로 연결해준다.

 

DFS를 통한 연결 요소 개수 세기

모든 정점에 대해 반복문을 수행하면서 방문하지 않은 정점을 찾는다.
방문하지 않은 정점을 시작으로 DFS를 수행하고, DFS를 호출하는 횟수가 연결 요소의 개수가 된다.
DFS 내에서는 현재 정점을 방문 처리하고, 연결된 모든 정점을 재귀적으로 방문한다.

 

 

 

 

DFS 구조

DFS는 깊이 우선 탐색으로, 한 정점에서 시작하여 연결된 정점을 모두 탐색한 후 다음 정점으로 이동한다.
재귀 함수 형태로 구현하며, 각 정점을 방문할 때마다 해당 정점을 방문 처리하고 연결된 정점을 순회한다.
모든 연결된 정점을 방문하고 나면 호출 스택에서 하나씩 빠져나와 이전 정점으로 돌아간다.