[백준] 11724 - 연결 요소의 개수(python)

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

11724번: 연결 요소의 개수

 

 

문제

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

 

입력

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

 

출력

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

---

소스코드

import sys
sys.setrecursionlimit(2500)

input = sys.stdin.readline
def dfs(v):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

n, m = map(int, input().split())
graph = [[] for i in range(n+1)]
visited = [False] * (n+1)
cnt = 0

for _ in range(m):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]

for x in range(1, n+1):
    if not visited[x]:
        dfs(x)
        cnt += 1
print(cnt)

 

소스코드 설명

DFS를 활용하여 구현하였다. 

1. python은 재귀 반복이 1000회로 지정되어 있어 sys의 setrecursionlimit 값을 지정해주어야 메모리 관련 에러로부터 자유로워질 수 있다.

2. 전형적인 dfs함수를 구현한다.

3. n,m을 입력받고 graph, visited 리스트를 선언 및 초기화한다.

4. m만큼 반복되는 횟수동안 dfs 활용이 가능한 그래프를 구현한다.

5. 연결 요소 횟수를 세기 위한 for문을 생성하고 dfs() 함수를 호출할 수 있도록 한다.

 

sys의 setrecursionlimit를 10**6으로 지정하였을 때에도 동일하게 메모리초과가 나타났다. 수를 2500으로 지정한 후 메모리 초과 없이 잘 수행되었다.