•
문제 설명
방향 없는(양방향) 그래프를 제시한 후, 해당 그래프에서 연결 요소의 개수를 구하는 문제이다.
개인적으로 시간초과로 인해 상당히 애먹었다.
실버 문제는 보통 기능 구현만 되어도 어느정도 통과가 되는데, 이 문제는 그렇지 않았다.
실버문제를 혼자 힘으로 풀지못해 아쉬었지만, 시간 초과를 줄이기 위한 많은 문법을 배울 수 있는 문제였다.
심지어 블로그에 작성된 정답 코드들을 그대로 사용해도 시간 초과가 표시되는 경우가 많았다. (케이스를 더 추가하신듯 하다.)
•
성공 코드
•
코드 설명
기본적으로 python의 재귀 한도는 1000이기 때문에 sys.setrecursionlimit() 를 사용하여 변경한다.
# 재귀 한도 수정
import sys
sys.setrecursionlimit(10**6)
...
Python
복사
dfs함수는 간단하다.
1.
노드 방문 처리
2.
노드와 연결된 다른 노드를 조회하여, 방문하지 않은 상태일 때 재귀함수 동작
...
def dfs(v):
# 방문 처리
visit[v] = True
# 해당 노드와 연결된 모든 노드 조회
for k in graph[v]:
# 방문하지 않은 노드일 경우 재귀함수 동작
if visit[k] != True:
dfs(k)
...
Python
복사
시간 단축을 한 첫 번째 부분이다.
기존의 input()으로 입력받지 않고, sys.stdin.readline() 로 입력받았다.
graph에는 각 노드와 연결된 노드들의 리스트를 저장할 수 있도록 2차원 배열을 만들었다.
...
# 시간 단축 부분(1)
# input() -> sys.stdin.readline()
input = sys.stdin.readline
N, M = map(int, input().split())
count = 0
visit = [False] * (N+1)
graph = [[] for _ in range(N+1)]
...
Python
복사
시간 단축을 한 두 번째 부분이다.
graph에 각 노드와 연결된 노드의 정보를 저장한다. [ EX) graph[1] → 노드1과 연결된 노드 리스트 저장 ]
이 graph를 정렬하여 낮은 노드부터 조회가 가능하도록 만들었다.
케이스의 정점의 개수가 매우 크다면 graph에 저장된 노드들의 리스트도 매우 많은 값이 저장될 것이다. 이때 정렬을 해준다면, 시간을 단축시킬 수 있다.
...
# 시간 단축 부분(2)
# 작은 노드부터 확인할 수 있도록, append된 배열을 정렬
for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
graph[a].sort()
graph[b].sort()
...
Python
복사
탐색이 한번 끝나면, 한 묶음의 탐색은 끝난 것이기 때문에 count 값을 증가시켜준다.
...
for i in range(1, N+1):
if visit[i] == 0:
dfs(i)
count += 1
print(count)
Python
복사