[ BOJ ] 11724 연결 요소의 개수 - python 문제풀이

11724 연결 요소의 개수

접근 : 연결리스트로 간선으로 이어진 점 정보를 저장하되 재귀로 계속 탐색해가면서 연결된 점들은 제외시켜나가기

풀이방법
1. 연결 리스트 만들기
2. 방문 여부(이미 연결시킨 점인지의 여부) 확인할 배열 v
3. 재귀로 방문한 적이 없는데, 연결되어있는 점을 찾아 v 갱신해주기

참고
python3 로 풀려면 sys를 불러와서 재귀 깊이를 따로 설정해줘야 런타임에러(Recursion Error)가 나지 않는다고 한다. (내 코드는 그렇게 설정해도 시간 초과가 난다) 그래서 pypy3로 풀었더니 통과.

def find(k):
    global v,d
    v[k]= 1 # 현재 도착한 점 방문 정보 갱신
    for num in d[k]: # 지금 도착한 점에서 이동할 수 있는 다른 정점
        if v[num] == 0: # 아직 가본 적 없는 정점이라면
            find(num) # 그 정점으로 이동
    return

N,M = map(int, input().split())
d = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

v = [0]*(N+1)
cnt = 0
for i in range(1,N+1):
    if v[i] == 0: # 아직 방문한 적이 없다면
        cnt += 1 # 새로운 요소의 시작
        find(i)
print(cnt)