[백준] 11724번 문제 (연결 요소의 개수) 파이썬(Python) 풀이

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

11724번: 연결 요소의 개수

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

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

for _ in range(m):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

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

count = 0

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

print(count)

처음에는 문제를 이해못했는데 알고보니 그래프가 몇개의 요소로 나뉘어져있나를 구하는 문제였다.

크게 복잡한 점은 없으나,

 

sys.setrecursionlimit(10**7)

dfs를 재귀적으로 사용했기 때문에 위와 같이 recursionlimit을 늘려주고,

 

dfs로 그래프의 노드를 하나씩 방문하다가 dfs함수가 종료되면 해당 그래프의 모든 노드의 방문이 끝났음을 의미한다.

이 방문이 한 번 끝날때마다 count를 1씩 더해주고 출력해주면 해당 count가 그래프의 연결 요소의 개수가 된다.

 

익숙한게 dfs라 dfs로 풀었지만 bfs로 풀어도 상관은 없을 것 같다.