[백준] 11724: 연결 요소의 개수 python 구현 / DFS, 런타임 에러 (RecursionError), 시간초과 해결

첫 시도에 해결할 줄 알았으나 5번이나 제출하고 해결한 문제 ㅎ

 

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

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

사실 문제 이해를 잘 못했다.

나와 같은 사람들을 위해 문제를 위한 그림 첨부 ! 

노드와 엣지를 선으로 연결 했을 때 빨간색 그룹과 파란색 그룹, 두 개의 그룹으로 나오게 된다. 이를 "연결 요소"라고 칭하고 그룹의 개수를 세는 문제.

 

풀이 

처음에는 DFS로 풀면 되겠다 싶어서 코드를 작성했건만 RuntimeError와 시간 초과 문제가 나타났다..

1. RuntimeError (RecursionError)

해당 문제는 sys 모듈을 사용하여 python에서 정의한 재귀의 최대 깊이보다 더 깊게 설정해주면 된다.

import sys    
sys.setrecursionlimit(10**7)

2. 시간 초과

해당 문제는 input값을 읽어오는 데서 발생하였다.

일반적으로 input() 함수와 비교하여 sys.stdin.readline() 함수의 속도가 더 빠르기 때문에 간선을 입력받기 위해 for문을 사용할 때는 sys.stdin.readline()을 사용하는 것이 유용하다. (-> 아니면 시간초과 에러 남)

근데.. 속도의 차이가 나는 이유는 무엇일까?

 

input() 함수의 경우에는 인자로 prompt message를 받을 수 있다.

n = input("값을 입력 하세요: ")

그러나 sys.stdin.readline()의 경우에는 prompt message를 받아 출력하는 기능이 없기 때문에 상대적으로 속도가 더 빠를 것으로 보인다.

뿐만 아니라 input()은 사용자가 입력하는 값 하나하나마다 버퍼에 저장하는 특징이 있다. 이때 입력의 종료가 되는 기준이 개행문자('\n')가 되므로, 개행문자를 생략한 값을 입력값에 저장할 수 있다.

반면에, sys.stdin.readline()은 개행 문자까지 포함한 하나의 줄을 한 번에 버퍼로 입력받는다.

 

아무튼 그래서! input() 대신 아래와 같이 적용해주면 된다는 말 ! 

for _ in range(m):
    n1, n2 = map(int, sys.stdin.readline().split())
    ad_list[n1].append(n2)
    ad_list[n2].append(n1)

 

CODE

+) 무방향 그래프이기 때문에 n1과 n2를 각각 다 append

import sys    
sys.setrecursionlimit(10**7) 

n, m = map(int, sys.stdin.readline().split())
ad_list = [[] for _ in range(n+1)]
for _ in range(m):
    n1, n2 = map(int, sys.stdin.readline().split())
    ad_list[n1].append(n2)
    ad_list[n2].append(n1)

def dfs(c_node):
    vst[c_node] = 1
    for i in ad_list[c_node]:
        if not vst[i]:  
            dfs(i)


vst = [0]*(n + 1)
result_cnt = 0
for i in range(1, n+1):
    if not vst[i]:
        result_cnt+=1
        dfs(i)

 

Reference

• https://afterdawncoding.tistory.com/37

 

(다음부터는 한번에 좀 풀고싶다..ㅠㅠ)