알고리즘/Python

[백준/Python] 11724번: 연결 요소의 개수

_SIHA_ 2022. 2. 11. 23:29

📖  문제 링크

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

 

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주

www.acmicpc.net

 

 

👩‍💻  문제풀이

 

일반적인 DFS, BFS문제였고, 연결된 그래프의 개수를 찾아 카운트해주면 되는 간단한 문제였다.

하지만 런타임 에러 때문에 원인을 찾느라 오래 걸렸다. 

 

배열의 인덱스 문제도 아니었고, 정답도 vscode에서는 정확히 나오고 있었기에 구글링을 시도..

파이썬은 재귀제한이 걸려있기 때문에 재귀 허용치를 넘어가면 런타임 에러가 발생된다고 한다.

따라서 아래와 같이 코드를 추가해주면 해결 완료!

 

sys.setrecursionlimit(10000)

 

 

 

  최종 코드

 

def dfs(x):
    check[x] = True
    for i in arr[x]:
        if check[i] == False:
            dfs(i)    
            

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

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

for i in range(m):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)
    
i = 1
sum = 0
while i!=(n+1):
    if check[i] == False:
        dfs(i)
        sum+=1        
    i+=1

print(sum)