[알고리즘] 백준11724 연결 요소의 개수 - 파이썬

 

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

11724번: 연결 요소의 개수

 

 

[풀이 코드]

import sys
from sys import stdin
sys.setrecursionlimit(10000)

input = stdin.readline

n, m = map(int, input().split())

graph = [[] for _ in range(n + 1)]
visited = [False] * (n+1)
cnt = 0

# 인접리스트
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)


def dfs(v):
    visited[v] = True
    for e in graph[v]:
        if visited[e] == False: # 연결되있으나 방문되지 않았다면
            dfs(e)

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

print(cnt)

 

- 방향 없는 그래프에서 연결 요소를 구하는 문제이다. 첫 번째 예제 입력을 예로 들면 노드 1, 2 5가 연결되어있고 노드 3, 4, 6이 연결돼있으므로 총 2개가 답이 되는 것이다.

 

- 처음에는 무작정 인접행렬을 그렸지만.. 이 문제는 인접 리스트로 푸는 것 같았다. 그리고 방문 여부를 확인하는 배열 visited 또한 필요하다. 

 

- dfs함수에서는 방문하면 재귀를 통해 visted배열에서 방문처리해줬고 아무래도 재귀의 시간제한 때문인지 sys.setrecursionlimit를 활용해야 했다.