11724

날짜 : 2022. 11. 01

사용 언어 : python

 

문제

 

 

코드

import sys
sys.setrecursionlimit(10**6) # 재귀 최댓값 증가(런타임 에러 방지)
n, m = map(int, sys.stdin.readline().split()) # 노드 개수, 간선 개수
graph = [[] for i in range(n+1)]
visited = [-1] * (n+1)
stack = []
cnt = 0

def dfs(idx):
    for i in graph[idx]:
        if visited[i] == -1: # 방문하지 않은 경우
            stack.append(i) # 연결된 노드 push
            visited[i] = cnt # 방문처리
            dfs(i) # dfs
            stack.pop() # 탈출
    return

for _ in range(m): # 간선 연결 입력
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

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

 

 

알게된 점

- 일반적인 DFS를 활용한 문제였다.

- 각 노드별 연결관계를 활용해 그래프를 만들고 방문처리를 하면서 연결개수를 구하면 되는 문제였다.

- 다만 테스트를 돌리는데 런타임 에러가 떠서 알아보니까 재귀 깊이를 설정하지 않아 발생한 것이었다.

- 그래서 sys.setrecursionlimit(10**6) 를 추가했고 문제를 해결할 수 있었다.

 

참고 사이트

-