백준 / 11724번 연결 요소의 개수 (DFS) / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 11724번 연결 요소의 개수

문제 사이트: https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

시간 제한메모리 제한제출정답맞힌 사람정답 비율

3 초

512 MB

99619

45181

29789

42.310%

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1 복사

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1 복사

2

예제 입력 2 복사

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2 복사

1

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: djm03178, seoo2001, YunGoon
• 잘못된 조건을 찾은 사람: songjuh

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

나의 풀이 DFS 로 풀었다.

문제를 풀면서 두가지 오류가 있었는데, 

첫번째는 DFS 의 최대 길이로 인한 오류 (재귀 호출은 1000번으로 제한된 파이썬 기본 설정)

두번째는 정점이 여러개이지만, 간선이 정점보다 작은 경우 각각의 정점을 처리 못해줘서 오류가 있었다.

 

첫번째 오류는

sys.setrecursionlimit(10**6)

 코드를 넣어 해결해주었다.

 

두번째 오류는 해당 코드로 진행하였을 때 발생했다. 

빈 노드여도 방문하지 않으면 연결을 1개로 쳐주지 못한 것이다.

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

예시로 입력값이

5 1 

2 3

으로 주어진다면, 2,3의 연결 간선은 계산 되지만 1,4,5 의 정점은 1개의 연결로 해당되지않아 출력값이 1로 나왔다.

 

다음과 같은 코드에서  노드가 비어있어도 해당 정점을 방문할 수 있도록 바꿔주었다.

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

해당 코드로 

5 1

2 3

값을 실행한다면 출력값이 4개로 나온다.

 

최종풀이

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m= map(int,input().split())
nodes = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = map(int,input().split())
    nodes[a].append(b)
    nodes[b].append(a)
cnt = 0

visited = [False] * (n+1)

def dfs(now):
    global cnt

    if visited[now] == True:
        return
    else:
        visited[now] = True

    if nodes[now] == []:
        return
    else:
        next = nodes[now]
        for i in range(len(next)):
            if visited[next[i]] == False:
                dfs(next[i])

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

print(cnt)

---

※ 알아야 할 것

- sys.setrecursionlimit(최대깊이) 를 통해 dfs함수를 쓸때 최대 깊이를 정하자!