[BOJ] 11724. 연결 요소의 개수 (python / java)

백준 11724. 연결 요소의 개수 (파이썬 / 자바)

DFS를 이용해서 하나의 그래프를 끝까지 탐색하고,

끝난 후에도 아직 방문하지 못한 새로운 시작점이 있다면

그래프의 개수를 추가한 후 그 그래프도 끝까지 탐색해 방문 표시를 한다.

 

파이썬

setrecursionlimit 적용하지 않을 경우 recursionError 발생

# [BOJ] <S2> 11724. 연결 요소의 개수
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)	# 추가 안해주면 틀림

def DFS(v):
    visited[v] = 1
    for n in L[v]:
        if visited[n] == False:
            DFS(n)


N, M = map(int, input().split())
L = [[] for _ in range(N + 1)]
visited = [0] * (N + 1)

for _ in range(M):
    a, b = map(int, input().split())
    L[a].append(b)
    L[b].append(a)

ans = 0

for i in range(1, N + 1):
    if visited[i] == False:
        DFS(i)
        ans += 1

print(ans)

자바

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

public class Main {
    static ArrayList<Integer>[] graph;
    static boolean[] visited;

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

        ArrayList<Integer> node = graph[v];
        for (int n : node) {
            if (!visited[n]) {
                DFS(n);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());   // 정점의 개수
        int M = Integer.parseInt(st.nextToken());   // 간선의 개수
        int ans = 0;

        graph = new ArrayList[N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i < N + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a].add(b);
            graph[b].add(a);
        }

        for (int i = 1; i < N + 1; i++) {
            if (!visited[i]) {
                ans++;
                DFS(i);
            }
        }

        System.out.println(ans);
    }
}

11724번: 연결 요소의 개수