문제

코드

DFS 활용

#######dfs  
import sys 
sys.setrecursionlimit(10**6) #깊이제한 늘리기 
input = sys.stdin.readline

def dfs(v):
    visited[v]=1

    for i in range(1,n+1):
        if visited[i]==0 and graph[v][i]==1:
            dfs(i)


n,m = map(int,input().split()) #n,m 입력 
graph = [[0]*(n+1) for _ in range(n+1)]
visited =[0 for _ in range(n+1)]
cnt =0

for i in range(m):
    u,v = map(int,input().split())
    graph[u][v]=1
    graph[v][u]=1

for i in range(1,n+1):
    if visited[i]!=1:
        dfs(i)
        cnt+=1

print(cnt)

bfs활용

import sys 
from collections import deque
sys.setrecursionlimit(10**6) #깊이제한 늘리기 
input = sys.stdin.readline

def bfs(v):
    queue =deque()
    queue.append(v)
    visited[v]=1
    while(queue):
        v = queue[0]
        queue.popleft()

        for i in range(1,n+1):
            if visited[i]==0 and graph[v][i]==1:
                queue.append(i)
                visited[i]=1


n,m = map(int,input().split()) #n,m 입력 
graph = [[0]*(n+1) for _ in range(n+1)]
visited =[0 for _ in range(n+1)]
cnt =0

for i in range(m):
    u,v = map(int,input().split())
    graph[u][v]=1
    graph[v][u]=1

for i in range(1,n+1):
    if visited[i]!=1:
        bfs(i)
        cnt+=1

print(cnt)

해설

그래프를 생성한 후 몇 개의 그래프가 생겼는지 확인 하는 문제이다.
이를 위해서 그래프탐색 알고리즘은 bfs,dfs중 선택할 수 있는데 시간,메모리적측면에서는 dfs가 더 효율적이였다.
그리고 여전히.. 행렬을 사용해서 쓸데없이 메모리를 많이 잡아먹는 고쳐아할 부분도 있긴하다.

쨌든 !
깊이를 탐색한 후 visit리스트에 값을 1로 바꿔주고
for문을 돌면서 만약 탐색하지 않은 그래프가 있다면 탐색하고 cnt를 올려주는 과정을 거쳤다.

깊이제한

그런데.. 런타임 에러가 떴다..
그래서 확인해보니 파이썬의 재귀의 깊이는 1000으로 매우 얕으므로 우리가 구해야할 재귀의 깊이까지

 sys.setrecursionlimit(10**6) #깊이제한 늘리기 

이를 사용해서 깊이제한을 늘려줘야한다..!