백준 11724(연결 요소의 개수) 파이썬

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

11724번: 연결 요소의 개수

이번에도 그래프 탐색 문제를 들고 왔다 이 문제는 DFS,BFS 둘다 풀리지만 난 DFS로 풀었다.

점점 그래프 탐색 문제에 자신감이 붙고 있다 술술 이해가 잘되고 다른문제도 풀리고 있다.

알고리즘에 묶이는 일은 줄어든거 같다.

설명은 코드에 주석처리로 해놓았다.

아래 코드를 보겠다.

import sys
sys.setrecursionlimit(10**8) #재귀깊이제한을 늘렸다.
input = sys.stdin.readline

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

graph=[[False]*(n+1) for _ in range(n+1)] # 노드들 간의 관계를 표시해줄 그래프 선언
visited = [False]*(n+1) # 방문 리스트 선언
cnt=0

for _ in range(m):
    x,y = map(int,input().split())
    graph[x][y]=graph[y][x]=True # 노드가 양방향 연결이기 때문에 스위칭해서 방문처리 해준다.\
            
def dfs(a):
    visited[a] = True # 시작한 노드 방문처리    
    for i in range(1,n+1):
        if visited[i] == False and graph[a][i] == True: # 방문하지 않았으며 인접노드가 방문처리 된 경우
            dfs(i)
            
for i in range(1,n+1):
    if visited[i] == False: #미방문 노드만 dfs문을 돌려 cnt를 늘려주며 연결요소의 개수를 카운트해준다.
        dfs(i)
        cnt+=1
        
print(cnt)

이 문제 같은경우 2가지 중요요소가 있다.

 

첫번째! 2번째줄인 재귀의 깊이제한을 수정해주는것이 중요하다.

파이썬 같은경우 재귀함수의 깊이제한이 있기 때문에 일정 깊이로 재귀가 반복되면 에러를 일으키기 때문에

깊이제한을 바꿔주는것이 중요하다.

 

두번째! input()으로 받는것이 아닌 sys.stdin.readline()으로 받는 것 이다.

필자는 첫번째 요소를 해결하였음에도 시간초과가 계속 떠서 이유를 몰랐다가 요즘 input()으로 계속 받는 버릇이 생겨서 이 문제도 자연스레 input()으로 받았다가 설마... 하면서 sys.stdin.readline() 수정하고 제출해보니 통과되었다.  여러 줄을 입력 받는 경우 sys.stdin.readline()이 더 빨리 처리 된다는것을 간과하고 있었다.

앞으로 이 점 유의하면서 문제를 풀어야 할 거 같다.