코딩 테스트 DFS 정리 (파이썬)

DFS

주요 인자들

인자 이름 설명 사용 예시

graph	그래프 자체	기본적으로 전역으로 처리
visited	방문 여부 체크용 (list 또는 set주로)	주로 지역, 중복 방지
path	지금까지의 경로 (list) 순서	경로 저장, 백트래킹
node / cur	현재 탐색 중인 노드	그래프 탐색 기본
depth / level	현재 깊이	제한 깊이, 최단/최장 거리 계산
acc / total / count	누적값 (합계, 개수 등)	누적 합, 조건 카운트
target	도달 목표	도달 여부 판단
parent	직전 노드	트리에서 사이클, 방향 판단
answer	결과 저장 리스트	경우의 수 저장 등

• 전역 변수들도 전달하는 이유는 테스트 용의

TIP

1. 모든 경우의 수를 끝까지 탐색하는 방법은 → 일반 DFS
2. 모든 경우의 수 중 조건 만족하는 해만 필요할 때, 또는 정답 하나만 빠르게 찾고 싶을 때 백트레킹 사용 (가지치기 필요시 백트래킹)
3. 2차원 배열 탐색은 방향 배열로 정리
4. 전역 vs 지역 구분
5. 백트래킹 시 방문 해제 필수
6. 리턴값이 있는 경우 처리 주의
   1. 하나의 경로나, 특정 시점시 종료할 경우 리턴값 사용
7. 노드 수가 많고 재귀 깊이가 크거나 백트래킹 경로 추적시 스택 DFS 사용

재귀DFS

# 프로그래머스 타겟넘버 
# 모든 경우의 수를 확인해야함 -> dfs  
# 필요 인자 total, level 
# 전역 변수 length
def solution(numbers, target):
    length = len(numbers)
    answer = 0

    def dfs(total, level):
        if level == length:
            if total == target:
                return 1
            return 0 
        
        return dfs(total+numbers[level],level+1) + dfs(total-numbers[level],level+1)
    
    return dfs(0,0)

DFS 백트레킹

• 모든 경우의 수 중 조건 만족하는 해만 필요할 때, 또는 정답 하나만 빠르게 찾고 싶을 때 백트레킹 사용 (가지치기 필요시 백트래킹)
• 조건에 따라 조기 종료
• 경로 복원, 상태 복원이 핵심
  • 경로를 구하는 문제의 경우 경로(path), 상태(visited)를 대부분 전역 변수로 처리하고 복원하자
  • 인자(지역변수)로 전달시
    • 리스트 복사 or 지역변수 리스트를 전달해서 복원
    • 경로, 상태 같은 리스트를 복사해서 인자로 전달할 수 있지만 이 경우도 복원 필요 → 복잡
    • 리스트 값 추가시 : path + [end] - 새로운 리스트를 넘기기

DFS 백트레킹 문제 풀이

(여행경로) 모든 경우의 수 탐색 → 정답 하나만 [ 경로, 상태 전역 처리 방식]

# 프로그래머스 여행경로 
# 모든 경우의 수 중 정답 하나만 찾고싶음 -> 재귀 + 백트래킹 + 가지치기
def solution(tickets):
    answer = []
    tickets.sort()

    used = [False] * len(tickets)
    path = ['ICN']

    def dfs():
        if len(path) == len(tickets) + 1:
            answer.append(path[:])  # ✅ 복사해서 저장 그냥 넣으면 얕은 복사
            return True

        for i, (start, end) in enumerate(tickets):
            if not used[i] and path[-1] == start:
                used[i] = True
                path.append(end)
                if dfs():
                    return True  # 정답 하나만 찾고 끝내기
                path.pop()       # ✅ 경로 복원
                used[i] = False  # ✅ 상태 복원
        return False # 정답을 찾지 못한  분기를 종료 

    dfs()
    return answer[0]

1. 가지치기 핵심 (정답 하나만 찾으면 다른 재귀를 모두 종료해야할떄)

# 여기서 조건을 충족하면 
if len(path) == len(tickets) + 1:
    answer.append(path[:])  # ✅ 복사해서 저장
    return True
    
# 여기서 True를 리턴받아서 더이상 아래 탐색으로 내려가지 않고 바로 종료 
if dfs():
    return True  # 정답 하나만 찾고 끝내기
    path.pop()       # ✅ 경로 복원
    used[i] = False

(여행경로) 모든 경우의 수 탐색 → 정답 하나만 [ 경로, 상태 인자로 지역변수 전달 방식]

# 프로그래머스 여행경로 
# 모든 경우의 수 중 정답 하나만 찾고싶음 -> 재귀 + 백트래킹 + 가지치기

def solution(tickets):
    routes = []
    tickets.sort()  # 사전순 정렬이 핵심

    def dfs(path, used):
        if len(used) == len(tickets):
            routes.append(path)
            return True  # ✅ 정답 하나 찾으면 종료 (가지치기)

        for i, (start, end) in enumerate(tickets):
            if not used[i] and path[-1] == start:
                used[i] = True
                if dfs(path + [end], used): # 여기서 true면 종료해버리기 
                    return True  # ✅ 찾으면 바로 리턴
                used[i] = False
        return False

    dfs(['ICN'], [False] * len(tickets))
    return routes[0]

(암호만들기) 모든 경우의 수 탐색 → 모든 정답 탐색 [ 경로, 상태 전역 처리 방식]

# 모든 경우의 수에서 조건 만족하는거 찾을떄 -> dfs 백트래킹
# 전역 변수 path, visited
# 인자 : depth, idx
# 가지치기 : 최대 모음, 자음 갯수를 구해서 이걸 넘으면 가지치기
# 모음 수 1 <= n <= len(aei) 이게 L-2보다 크면 이걸로  자음 수 2<= n <= len(bcd) 이게 L -1보다 크면 이걸로
L, C = map(int, input().split())
li = sorted(input().split())
path = []
visited = [False] * C
def dfs(depth,idx):
    if depth == L:
        ac = sum([1 for i in path if i in ("a","e","i","o","u")])
        bc = L - ac

        if ac >=1 and bc>=2:
            print("".join(path))

    for i in range(idx, C):
        if not visited[i]:
            visited[i] = 1
            path.append(li[i])
            dfs(depth + 1, i + 1)
            visited[i] = 0
            path.pop()

dfs(0,0)

4 6
a t c i s w

(암호만들기) 모든 경우의 수 탐색 → 정답 하나만 [ 경로 인자로 지역변수 전달 방식, 상태 x]

# 백준 암호 만들기
# 모든 경우의 수에서 조건 만족하는거 찾을떄 -> dfs 백트래킹
# 인자: node_id, path, a(모음수), b(자음수)
# 가지치기 :  a >= 1 and b >= 2 and len(path) == L 가지치기
L, C = map(int, input().split())
li = sorted(input().split())

answer = []
aei_set = {"a", "e", "i", "o", "u"}

def dfs(node_id, path, a, b):
    if node_id == C:
        if a >= 1 and b >= 2 and len(path) == L:
            answer.append("".join(path))
        return

    node = li[node_id]

    # 안 넣기
    dfs(node_id + 1, path, a, b)

    # 넣기
    if node in aei_set:
        dfs(node_id + 1, path + [node], a + 1, b)
    else:
        dfs(node_id + 1, path + [node], a, b + 1)

dfs(0, [], 0, 0)

for p in sorted(answer):
    print(p)

스택 DFS

• 백트래킹 이걸로도 가능
• 재귀 깊이가 큰 경우 스택 쓰는게 좋음

(암호만들기)

from collections import deque

L, C = map(int, input().split())
li = sorted(input().split())
vowels = {"a", "e", "i", "o", "u"}

stack = deque()
stack.append(([], 0))  # (path, start_idx)

while stack:
    path, idx = stack.pop()

    if len(path) == L:
        ac = sum(1 for ch in path if ch in vowels)
        bc = L - ac
        if ac >= 1 and bc >= 2:
            print("".join(path))
        continue

    for i in range(C - 1, idx - 1, -1):  # 역순으로 넣어야 사전순 출력
        if li[i] not in path:  # 중복 제거용 (visited 대체)
            stack.append((path + [li[i]], i + 1))
            # 여기서 첫번째에 ([w],5), ([s],4), ([i],3), ([c],2), 
            ([t],1), ([a],0) 순으로 스택에 들어가고 그다음 
            # 뒤에 a부터 빼와서 실행하는거  
4 6
a t c i s w

• 백준 2606 – 바이러스 풀어보기

# 방문 순서
graph = {
    'A': ['B', 'C'], # 여기서 B를 먼저 방문해야함
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

def dfs_stack(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            # 역순으로 넣어야 탐색 순서 일치 -pop으로 뒤부터 꺼내니까 먼저있는 B를 뽑으려면 reverse 해줘야함
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited
result = dfs_stack(graph, 'A')
print(result)
{'A', 'B', 'D', 'E', 'C', 'F'}