[백준] 11724번 무방향 그래프 DFS BFS - 재귀에러

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

---

1. DFS - 재귀함수로 그래프 탐색

재귀함수로 구현한 DFS로 풀었더니 런타임 에러가 뜬다.

아마도 재귀 함수가 문제 제한 보다 더 많이 중첩되어서 에러가 뜨는 것 같다.

# BOJ_11724
# dfs
def dfs(start, visited):
    global graph
    if visited[start]:
        return False
    visited[start] = True
    for node in graph[start]:
        if visited[node] == False:
            dfs(node, visited)
            return True
    return False


# 입력
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
# print(graph)


# dfs를 이용하여 연결 덩어리들의 갯수를 구한다.
link_count = 0
for i in range(1, n + 1):
    if dfs(i, visited) == True:
        link_count += 1
print(link_count)

sys.setrecursionlimit(5000)

을 넣어주면 해결되긴 한다.

---

2. DFS - 스택으로 탐색

python3로는 시간 초과가 나온다.

아오..

(pypy3는 정답으로 나오는 이상한 채점 구조)

 

# BOJ_11724
# dfs
def dfs(start, visited):
    global graph
    # stack에 탐색할 노드를 추가한다.
    stack = []
    stack.append(start)
    while stack:
        node = stack.pop()
        # 방문한 노드이면 그 노드는 이미 체크했으므로 스킵한다.
        if visited[node]:
            continue
        # 한번도 방문하지 않았다면 더 탐색한다.
        else:
            visited[node] = True
            stack.extend(graph[node])
    return


# 입력
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


# dfs를 이용하여 연결 덩어리들의 갯수를 구한다.
link_count = 0
for i in range(1, n + 1):
    # 해당 노드를 방문한 적이 없으면
    if not visited[i]: # 새로운 덩어리이면
        link_count += 1
        dfs(i, visited)
        # print(i, visited)
print(link_count)

 

막간의 팁!

extend 와 append 차이

extend는 리스트의 성분들을 붙여주고,

append는 리스트 자체를 붙여준다.

 

https://conanglog.tistory.com/171

[python] extend 함수

 

 

---

3. BFS - 큐로 탐색

하지만 이또한 python3는 시간초과로 나오고, pypy3는 정답으로 나온다.

from collections import deque

# bfs
def bfs(start, visited):
    global graph
    q = deque(graph[start])
    visited[start] = True
    while q:
        node = q.popleft()
        if not visited[node]:
            visited[node] = True
            q.extend(graph[node])
    return


# 입력
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


link_count = 0
for i in range(1, n + 1):
    # 해당 노드를 방문한 적이 없으면
    if not visited[i]: # 새로운 덩어리이면
        link_count += 1
        bfs(i, visited)
        # print(i, visited)
print(link_count)

 

 

참고:

https://velog.io/@kimdanni/BFS-DFS-%EA%B5%AC%ED%98%84-python

BFS DFS 구현 (python)