[파이썬, Python] 백준 11724: 연결 요소의 개수

문제

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

11724번: 연결 요소의 개수

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
cnt = 0

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(v):
    visited[v] = True
    for i in graph[v]:
        if visited[i] == False:
            visited[i] = True
            dfs(i)

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

print(cnt)

설명

우선 파이썬에서 dfs를 사용할 때 중요한 부분이 바로 3번 라인의 'sys.setrecursionlimit(10**7)' 이 부분이다.
파이썬은 자체적으로 재귀의 제한을 두고 있기 때문에 이를 이용해서 제한을 늘려주어야 무리 없이 문제 풀이가 가능하다.

우선 각 그래프의 입력을 받아주자.

그리고 dfs를 정의하면 되는데,
graph의 [v]에 대하여 v 리스트의 요소 중 방문한 기록이 없는 노드에 대해 방문처리를 해주고,
그 노드에 대해서 또 dfs를 돌려준다.

dfs를 정의하고 정점의 개수에 맞춰 dfs를 실시한다.
이 때, 방문하지 않은 노드가 있다면 기존의 노드들과 연결되지 않았다는 뜻이므로 cnt를 1개 늘려준다.

cnt를 출력한다.