백준 11724번 연결요소의 개수 [Python]

[Silver II] 연결 요소의 개수 - 11724

문제 링크

성능 요약

메모리: 64936 KB, 시간: 672 ms

분류

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

제출 일자

2024년 3월 30일 17:39:00

문제 설명

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

입력

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

출력

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

풀이

문제를 보자마자 그래프로 접근할 수 있는 문제라고 생각했다. 매번 그래프 문제에서 BFS만 쓰다가 DFS를 까먹을까봐 이번엔 둘 다 코드를 작성해보았다. 참고로 파이썬은 재귀호출이 1,000번으로 제한되어 있으므로, DFS에서는 sys.recursionlimit()를 이용하여 재귀호출 횟수를 넉넉하게 늘려준다.

전체 코드

# BFS를 이용한 코드

import sys
input = sys.stdin.readline

def BFS(n):
    q = [] # 탐색 정점 리스트
    q.append(n) # 탐색 정점 저장
    v[n] = 1 # 방문 표시

    while q: # 탐색할 곳이 없을때 까지,
        c = q.pop() # q에서 탐색 정점을 꺼내서 c에 저장
        for i in graph[c]: # 정점과 연결된 정점들을 탐색
            if not v[i]: # 방문하지 않은 정점이면,
                q.append(i) # 이 정점을 다음 탐색 정점리스트에 추가
                v[i] = 1 # 이 정점을 방문 표시


N,M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for i in range(M):
    u, v = map(int, input().split())

    # 무방향 그래프이므로 연결된 두 정점에 서로를 추가
    graph[u].append(v)
    graph[v].append(u)

v = [0] * (N+1)
cnt = 0
for i in range(1, N+1): # 이전에 방문을 마친 정점들은 스킵
    if not v[i]: # 방문하지 않은 정점이면,
        BFS(i) # 이 정점에 연결된 정점들을 탐색(연결요소)
        cnt += 1 # 연결요소 +1

print(cnt)

# DFS를 이용한 코드

import sys
sys.setrecursionlimit(10**6) # 재귀호출 횟수제한 조정
input = sys.stdin.readline

def DFS(n):
    v[n] = 1 # 방문 표시

    for i in graph[n]: # 정점과 연결된 정점들을 탐색
        if not v[i]: # 방문하지 않은 정점이면,
            v[i] = 1 # 이 정점을 방문 표시
            DFS(i) # 이 정점에 연결되어있는 정점을 재귀호출로 탐색


N,M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for i in range(M):
    u, v = map(int, input().split())

     # 무방향 그래프이므로 연결된 두 정점에 서로를 추가
    graph[u].append(v)
    graph[v].append(u)

v = [0] * (N+1)
cnt = 0
for i in range(1, N+1): # 이전에 방문을 마친 정점들은 스킵
    if not v[i]: # 방문하지 않은 정점이면,
        DFS(i) # 이 정점에 연결된 정점들을 탐색(연결요소)
        cnt += 1 # 연결요소 +1

print(cnt)