[백준] 11724 연결 요소의 개수 / 파이썬 (Python)

문제 링크: https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

thinking

말만 어렵지 별 거 아니었다. (별 거 맞음)
연결 요소란,

뭔솔....?

.... 됐다.
그냥 쉽게 생각하려면 예제를 그래프로 직접 그려보면 된다.

서로 다른 그래프가 2개가 있는 게 아니라, 하나의 그래프에서 연결이 안된 것 뿐이다. 
각각 나누어진 것을 연결요소라고 부르고, 저 2개를 세면 되는 문제이다.
dfs와 bfs 두 가지 방식 모두 사용할 수 있는 문제이지만, dfs가 더 익숙해서 dfs로 문제를 풀었다.

연결 요소의 개수 = dfs를 실행한 횟수

dfs는 한 놈만 패는 애라고 했다... 그 말은 즉슨, 하나의 연결요소의 끝까지 파고들어서 연결된 노드를 확인하고,
다음(방문하지 않은) 연결요소로 넘어간다는 뜻이다.
dfs를 몇 번 실행하는 지 cnt 변수를 선언하여 dfs()를 재귀호출 하기 전에 끼워넣으면 된다.

# 연결 요소의 개수 = dfs를 실행한 횟수
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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)

visited = [0] * (n + 1)
cnt = 0


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


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

 

오늘의 실수

- 파이썬 최대 재귀 깊이 제한

sys.setrecursionlimit(10**7)

파이썬은 최대 재귀 횟수를 1000번까지 제한하고 있다. 그러므로 문제에서 제시하는 조건을 잘 읽고, 재귀 제한을 푸는 것이 중요하다! 재귀 제한을 해제하지 않으면 백준 채점에서 끝도 없는 런타임 에러를 만날 수 있다.

- for문 안에서는 index 잘 보자

for i in range(1, n+1):
    if visited[i] == 0:
        cnt += 1
        dfs(i) # v가 아니라 i로 돌려야함

처음에 코드를 실행했을때 출력이 이상해서 한참 쳐다보니 dfs를 for문에 넣어놓고 v로 돌리고 있었다...
자잘한 실수로 전체를 보는 수고로움이 필요하니 정신 차리고 잘 적자...!!
 
이번엔 DFS로 풀었지만 다음에 복습할때 BFS로 풀어서 해당 글에 추가해야겠다!