[백준_python] 연결 요소의 개수 || 11724 (시간초과, 런타임에러(recursionerror)

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

DFS를 이용할까 했는데, BFS로 해주기 시작했다.
코드를 짜면서 바로 전에 풀었던 DFS, BFS 관련 문제들과 다를게 없는 것 같아서 다행이라고 생각하면서
풀어주었다.
똑같이 큐로 시작 정점을 저장해주며, 방문하지 않고 간선이 이어준 곳을 방문 체크를 해주며 큐에 값을 넣어주는 방식으로 함수를 작성을 해주었다.
그 후, 연결 요소를 세어주는 것이다보니, 탐색이 끊기는 부분을 찾아주어야 했기 때문에,
방문이 되지 않는 곳을 찾아주어 탐색을 하도록 해주며 값을 계산해주었다.

너비 우선 탐색(BFS)

# 연결 요소의 개수(bfs, 시간초과)

n, m = map(int, input().split(' '))  # n : 정점의 개수, m : 간선의 개수
graph = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, input().split(' '))
    graph[a][b] = graph[b][a] = 1  # 간선의 개수만큼 정점끼리 연결해준다


def BFS(start):
    queue = [start]
    while queue:
        start = queue.pop(0)
        for i in range(1, n+1):
            if not visited[i] and graph[start][i] == 1:  # 방문하지 않았고, 간선이 존재한다면
                queue.append(i)
                visited[i] = True


count = 0  # 연결 요소의 개수
for i in range(1, n+1):
    if not visited[i]: #방문하지 못한 곳을 시작 정점으로 하여서 개수를 세어준다.
        BFS(i)
        count += 1
print(count)

input()보다 sys로 입력을 받아주면 시간 초과 문제가 해결된다!

# 연결 요소의 개수(bfs)

import sys

n, m = map(int, sys.stdin.readline().split(' '))
graph = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split(' '))
    graph[a][b] = graph[b][a] = 1


def BFS(start):
    queue = [start]
    while queue:
        start = queue.pop(0)
        for i in range(1, n+1):
            if not visited[i] and graph[start][i] == 1:  # 방문하지 않았고, 간선이 존재한다면
                queue.append(i)
                visited[i] = True


count = 0
for i in range(1, n+1):
    if not visited[i]:
        BFS(i)
        count += 1
print(count)

---

깊이 우선 탐색(DFS)

 

# 연결 요소의 개수(dfs, 런타임 에러(recursionerror))

n, m = map(int, input().split(' '))
graph = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, input().split(' '))
    graph[a][b] = graph[b][a] = 1


def DFS(start):
    visited[start] = True
    for i in range(1, n+1):
        if not visited[i] and graph[start][i] == 1:
            DFS(i)


count = 0
for i in range(1, n+1):
    if not visited[i]:
        DFS(i)
        count += 1
print(count)

런타임 에러(recursionerror)가 발생했다
원인은 python에서 정해준 깊이 탐색 길이를 벗어나게 되면 이런 오류가 발생한다고 한다.
sys.setrecursionlimit(10000) 를 추가해주어 길이를 변경해주어야 한다.

# 연결 요소의 개수(dfs)

import sys
sys.setrecursionlimit(10000) #python이 정한 최대 깊이를 더 깊게 변경해줌

n, m = map(int, sys.stdin.readline().split(' '))
graph = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split(' '))
    graph[a][b] = graph[b][a] = 1


def DFS(start):
    visited[start] = True
    for i in range(1, n+1):
        if not visited[i] and graph[start][i] == 1:
            DFS(i)


count = 0
for i in range(1, n+1):
    if not visited[i]:
        DFS(i)
        count += 1
print(count)