Inflearn Community Q&A

usagi1

asked

[Python] DFS Algorithm Understandable Even for Liberal Arts Students! - Introductory Edition

Number of connected elements (Baekjoon 11724)

itertools, sys같은 STL을 사용할 수 없는 경우 질문드립니다.(백준 11724)

Written on

Edited

안녕하세요. 코드를 쉽게 짜주셔서 코딩테스트 입문으로 잘 듣고 있습니다.

다름이아니라 이번에 코딩테스트를 보는데 파이썬에서 itertools와 sys같은 STL을 사용하지 못하는 제약조건이 있습니다.

그래서 백준 11724 문제에서 맨 위 sys를 사용하는 세 문장(import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline)을 빼고 제출해보니 런타임 에러 (RecursionError)가 발생합니다.

이러한 경우에는 코드를 어떻게 수정해서 할 수 있을지 궁금합니다.

그리고 "수업노트 보기"에 큐를 사용하는 강의에서 설명하지 않는 다른 코드가 있는데 이건 뭔지 궁금합니다.

python코딩-테스트알고리즘dfspython3

Quiz

깊이 우선 탐색(DFS)의 주요 탐색 전략은 무엇인가요?

인접 노드 우선

최대한 깊이 탐색

모든 노드 동시

탐색 경로 무시

Answer 1

gaebaljob

Instructor

1. `STL 제약이 있을 경우`

파이썬은 기본적으로 프로그램이 무한 루프에 빠져 다운되는 것을 막기 위해, 함수가 자기 자신을 호출하는 '재귀 깊이'를 약 1,000번으로 제한하고 있습니다.

sys.setrecursionlimit을 사용할 수 없는 상황이라면, 재귀 함수 대신 스택(Stack)을 활용한 반복문 형태의 DFS로 코드를 수정해야 합니다. 파이썬의 기본 리스트는 append()와 pop()을 지원하므로 외부 모듈 없이도 완벽하게 스택으로 활용할 수 있습니다.

작성해주셨던 코드를 기반으로, 모듈 임포트 없이 기본 기능만 사용하여 수정한 반복문 DFS 코드는 다음과 같습니다.

# sys 모듈을 비롯한 어떤 import도 사용하지 않습니다.

N, M = map(int, input().split())

# defaultdict 대신 기본 딕셔너리와 리스트 컴프리헨션 사용
dic = {i: [] for i in range(1, N + 1)}
visited = set()
result = 0

for _ in range(M):
    x, y = map(int, input().split())
    dic[x].append(y)
    dic[y].append(x)

# 재귀 대신 스택(리스트)을 사용한 반복문 DFS
def dfs_iterative(start_node):
    stack = [start_node] # 탐색을 시작할 노드를 스택에 넣습니다.
    
    while stack: # 스택에 노드가 남아있는 동안 계속 반복
        node = stack.pop() # 스택의 가장 위(마지막)에 있는 노드를 꺼냄
        
        if node not in visited:
            visited.add(node)
            # 현재 노드와 연결된 방문하지 않은 노드들을 스택에 추가
            for n in dic[node]:
                if n not in visited:
                    stack.append(n)

# 모든 정점을 순회하며 연결 요소 찾기
for i in range(1, N + 1):
    if i not in visited:
        dfs_iterative(i)
        result += 1

print(result)

sys.stdin.readline을 쓰지 못해 input()을 사용하면 속도가 다소 느려집니다. 하지만 모듈 사용을 막아둔 실제 코딩테스트라면, 출제자 역시 이를 감안하여 시간 제한을 넉넉하게 두거나 테스트 케이스의 크기를 조절해 두었을 테니 이 부분은 너무 걱정하지 않으셔도 됩니다.

2. 수업 노트에 있는 Queue를 사용하는 코드

수업 노트에서 보신 코드는 DFS가 아니라 BFS(Breadth-First Search, 너비 우선 탐색) 알고리즘입니다.

DFS (깊이 우선 탐색): 한 방향으로 갈 수 있을 때까지 깊게 파고드는 방식입니다. (질문자님이 처음에 작성하신 방식)
BFS (너비 우선 탐색): 시작점에서 가까운 이웃 노드들부터 물결이 퍼지듯 넓게 탐색하는 방식입니다.

11724번 문제처럼 단순히 '그래프가 몇 덩어리로 나뉘어 있는지'를 찾는 문제에서는 노드를 빠짐없이 방문하기만 하면 되므로, DFS와 BFS 중 편한 것을 선택해서 풀면 됩니다. 특히 BFS는 구조적으로 재귀를 사용하지 않기 때문에 지금처럼 RecursionError를 피해야 할 때 아주 좋은 대안입니다.

⚠ 단, 주의할 점이 하나 있습니다.

질문자님께서 겪고 계신 제약 조건이 import 자체를 완전히 금지하는 것이라면, 수업 노트에 있는 from collections import deque 역시 사용할 수 없습니다. collections도 파이썬의 내장 라이브러리이기 때문입니다.

만약 deque도 쓸 수 없는 상황이라면, 앞서 스택을 만들 때처럼 파이썬 기본 리스트를 큐로 활용해야 합니다.

기본 리스트에서 맨 앞의 데이터를 꺼내는 pop(0)은 deque보다 속도가 느립니다. 하지만 이 문제에서는 정점(N)이 최대 1,000개로 매우 작기 때문에 기본 리스트만으로도 시간 초과 없이 무사히 통과할 수 있습니다.