[백준 - Python] 11724. 연결 요소의 개수 (DFS/BFS)

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

11724번: 연결 요소의 개수

 

코드

import sys
sys.setrecursionlimit(10 ** 6)

input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

cnt = 0
for i in range(1, n+1):
    if not visited[i]:
        dfs(graph, i, visited)
        cnt += 1

print(cnt)

 

복잡한 설명은 없었고, 하나의 유형으로 볼 수 있을 문제였다.

단순히 그래프의 정점 개수와 간선의 개수가 주어지고

간선으로 연결된 요소가 몇 개 인지 구하는 문제였다.

 

이코테 파이썬 책에서 배운 dfs 함수를 출력 부분을 제외하고 그대로 활용했고,

1부터 n까지 돌며 방문하지 않은 노드일 경우에 dfs를 호출하였다.

또한 요소의 개수를 세어주기 위해 dfs가 호출될 때마다 카운팅을 해주었다.

 

해당 문제에서 배운 점은 크게 두 가지이다.

 

1. 그래프에서 dfs(혹은 bfs)를 활용해 연결 요소의 개수를 구하는 방법

2. 재귀를 활용한 풀이에서 sys.setrecursionlimit() 의 사용

 

2번에 대해 더 자세히 알아보자.

 

코딩 테스트에서 재귀를 사용하여 풀어야 하는 상황을 마주하면,

import sys
sys.setrecursionlimit(10**6)

 

위의 코드를 필수적으로 사용해야 한다.

 

파이썬의 기본 재귀 깊이는 1000의 제한을 가진다.

따라서 재귀를 사용해 문제를 풀 경우에 깊이 제한에 걸리게 되는데,

더 심각한 문제는,

코딩 테스트 환경에서는 에러 메세지를 볼 수 없어 해결을 하지 못할 수도 있다는 점이다.

 

또한, pypy에서는 sys.setrecursionlimit() 으로 재귀의 최대 깊이를 설정할 수 없다.

 

위의 코드를 반드시 숙지하여 재귀를 활용해 문제를 풀 때

꼭 활용하도록 하자 !

 

 

참고 자료

https://fuzzysound.github.io/sys-setrecursionlimit