[백준|파이썬] 11724: 연결 요소의 개수 (실버2)

문제

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

11724번: 연결 요소의 개수

 

 

🐍파이썬

import sys
sys.setrecursionlimit(10**6)	#최대 재귀깊이를 조절하여 런타임에러 해결

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visited = [0 for _ in range(n+1)]

def dfs(v):
    visited[v] = 1	#방문처리
    # print(v, end= " ")
    for i in graph[v]:
        if visited[i] == 0:	#방문하지 않았을 경우
            dfs(i)	#방문

answer = 0
for i in range(1, n+1):
    if visited[i] == 0:	#방문하지 않은 노드에 대한 dfs실행
        dfs(i)
        answer += 1	#재귀가 종료되면 간선이 연결된 구역의 갯수를 체크
print(answer)

간선으로 연결된 구역의 갯수를 찾는 문제였다

DFS를 이용해 해결하였다.