[백준] 11724번 : 연결 요소의 개수 (파이썬)

문제

첫번째 제출(런타임 에러)

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
g=[[] for i in range(n+1)] #n+1개의 노드를 갖는 그래프 생성
cnt=0

for _ in range(m):
    u,v=map(int,input().split())
    g[u].append(v)
    g[v].append(u)

visited=[0]*(n+1) #방문한 노드 저장, 방문했으면 1로 변경

def dfs(n):
    visited[n]=1
    for i in g[n]:
        if visited[i]==0:#방문하지 않았다면
            dfs(i)#방문처리

for j in range(1,n+1):
    if visited[j]==0:
        cnt+=1
        dfs(j)
print(cnt)

파이썬의 기본 재귀 깊이는 1000이라고 한다. dfs함수를 재귀적으로 호출하고 있으므로 깊이를 확장해주어야 한다. (참고: https://www.acmicpc.net/board/view/85228)

최종 답안

import sys
sys.setrecursionlimit(10**6)#파이썬 재귀 깊이 확장 1000->10^6
input = sys.stdin.readline

n,m=map(int,input().split())
g=[[] for i in range(n+1)] #n+1개의 노드를 갖는 그래프
cnt=0

for _ in range(m):
    u,v=map(int,input().split())
    g[u].append(v)
    g[v].append(u)

visited=[0]*(n+1) #방문한 노드 저장, 방문했으면 1로 변경

def dfs(n):
    visited[n]=1
    for i in g[n]:
        if visited[i]==0:#방문하지 않았다면
            dfs(i)#방문처리

for j in range(1,n+1):
    if visited[j]==0:
        cnt+=1
        dfs(j)
print(cnt)

접근 방법

• dfs 문제, 지난번에 풀었던 바이러스 문제와 유사한 문제이다.
• 연결 요소는 각 노드들이 연결된 구역이라고 생각하고 접근하면 된다.
• 방문한 노드들은 1로, 방문하지 않은 노드는 0으로 처리해 값이 0이라면 처음 방문한 노드이므로 cnt값을 1증가시켜준다.