문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
출력
첫째 줄에 연결 요소의 개수를 출력한다.
#11742 연결 요소의 개수
import sys
sys.setrecursionlimit(10000) # 재귀 제한을 확대해야 함.
def dfs(x):
if not visited[x]:
visited[x] = True
for i in graph[x]:
dfs(i)
return True
return False #방문했었으면 return False
#True가 될 때마다 1을 더한다
n,m = map(int,input().split()) # [[],[2,3],[1,4]]
visited = [False] * (n + 1)
graph = [[] for _ in range(n+1)] #0 포함해서 생성
for i in range(m):
a,b = map(int,sys.stdin.readline().split()) # 1,2
graph[a].append(b)
graph[b].append(a)
sum = 0
for i in range(1, n+1):
if dfs(i) == True:
sum+=1
print(sum)
틀렸던 이유:
1) Recursion Error가 나서 sys.setrecursionlimit(10000)를 해주어야 함
- 이건 범위가 어떻게 주어졌을때 발생하는지 몰라서 시간 날때 제대로 공부해봐야겠다.
2) 상하좌우로 가는 문제의 경우 dfs 인자의 범위를 정해주었는데, 여기선 그럴 필요 없는데 범위를 줬었다, 그것도 틀리게
느낀 점:
- dfs 반환값이 True일때만 +1을 하는 문제의 경우, if (방문 처리 안되었을 경우)에 재귀, 그리고 return true하고 else(아닐 시)에는 return False를 해주어야 +1이 안된다.
- 1부터 시작하는 경우, 0은 생성하지만 무시하기 때문에, graph는 n+1만큼, visited도 n+1 만큼, 0은 무시하기 때문에 반복문은 1부터 n+1까지 돌린다.
Self Refiner