[알고리즘 / 백준] 11724 - 연결 요소의 개수

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

문제는 위와 같으며 이 경우는 일반적인 DFS 를 통해 연결 요소를 확인하고 그 수를 세면 해결할 수 있는 문제입니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin


# 일반적인 DFS 수행 (연결 요소 찾기)
def dfs(start):
    queue = [start]

    while queue:
        node = queue.pop()
        if not visited[node]:  # 아직 방문하지 않은 노드인 경우
        	visited[node] = True  # 해당 노드를 방문 처리하고
            queue.extend(graph[node])  # 해당 노드와 연결된 노드를 다시 큐에 저장


n, m = map(int, stdin.readline().split())
graph = [[] for _ in range(1001)]
for _ in range(m):
    u, v = map(int, stdin.readline().split())
    # 무방향 그래프이기 때문에 양쪽 정점을 모두 저장해줍니다.
    graph[u].append(v)
    graph[v].append(u)

visited = [False] * 1001
count = 0
for i in range(1, n + 1):
    if not visited[i]:  # 아직 연결되지 않은 경우
        dfs(i)  # 연결 요소 모두 방문
        count += 1  # 연결 요소 그룹 확인 후 연결 요소 수 +1
print(count)

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    private static List<ArrayList<Integer>> graph;
    private static boolean[] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        for (int i = 0; i < n + 1; 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);
        }

        visited = new boolean[n + 1];
        int count = 0;

        for (int i = 1; i < n + 1; i++) {
            if (!visited[i]) {  // 아직 방문하지 않은(연결되지 않은) 요소인 경우
                dfs(i);  // 연결 요소를 모두 확인하고
                count += 1;  // 연결 요소 개수를 +1
            }
        }

        System.out.println(count);
    }

    private static void dfs(int start) {
        visited[start] = true;  // 해당 요소를 방문 처리 하고

        for (int n : graph.get(start)) {  // 해당 요소와 연결된 요소들을 차례로 확인하면서
            if (!visited[n]) {  // 아직 방문(연결)하지 않은 요소인 경우
                dfs(n);  // 방문 처리 함수 재귀 수행
            }
        }
    }
}