DFS

전체 순회시

from collections import deque

def dfs(graph, start):
    visited = []
    stack = deque([start])  # stack처럼 사용

    while stack:
        node = stack.pop()  # top(오른쪽)에서 꺼냄; LIFO

        if node not in visited:  # 이미 방문한 경우 더 아래로 탐색하지 않음
            visited.append(node)  # 방문 리스트에 추가
            stack.extend(reversed(graph[node]) # 왼쪽 자식부터 pop되도록 reverse

    return visited

목표 탐색시

from collections import deque

def dfs(graph, start, goal):
    visited = []
    stack = deque([start])  # stack처럼 사용

    while stack:
        node = stack.pop()  # top(오른쪽)에서 꺼냄; LIFO

        if node == goal:
            visited.append(node)
            return visited  # goal 찾으면 종료

        if node not in visited:
            visited.append(node)
            stack.extend(reversed(graph[node]))  # 왼쪽 자식부터 pop되도록 reverse

    return visited  # goal이 없으면 전체 방문 결과 반환

BFS

전체순회시

from collections import deque

def bfs(graph, start):
    visited = []
    queue = deque([start])  # queue처럼 사용

    while queue:
        node = queue.popleft()  # 왼쪽에서 꺼냄; FIFO

        if node not in visited:  # 이미 방문한 경우 더 아래로 탐색하지 않음
            visited.append(node)  # 방문 리스트에 추가
            queue.extend(graph[node]) # 자식들 추가함

    return visited

목표 탐색시

from collections import deque

def bfs(graph, start, goal):
    visited = []
    queue = deque([start])  # queue처럼 사용

    while queue:
        node = queue.popleft()  # FIFO

        if node == goal:
            visited.append(node)
            return visited  # goal 발견 시 바로 종료

        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])

    return visited  # goal이 없으면 전체 탐색 결과 반환

깊이 제한 탐색 (DLS)

from collections import deque

def dls(graph, start, limit):
    visited = []
    stack = deque([(start, 0)])  # 스택: (노드, 현재 깊이) 형태로 저장

    while stack:
        node, depth = stack.pop()  # 스택의 top에서 노드와 그 깊이 꺼냄

        if node not in visited:
            visited.append(node)  # 아직 방문하지 않은 노드라면 방문 처리

            if depth < limit:  # 현재 깊이가 제한보다 작을 경우만 자식 노드 탐색
                for neighbor in reversed(graph[node]):  # 왼쪽 자식부터 pop되게 역순으로 push
                    stack.append((neighbor, depth + 1))  # 자식 노드와 그 깊이를 push

    return visited  # 방문한 노드들의 순서 반환

• 노드를 현재 깊이와 함께 튜플로 스택에 저장한다.
• 현재 깊이가 제한보다 작을 경우만 자식 노드를 탐색하는 방식으로 DFS를 순회한다.

반복 심화 탐색 (ID-DFS)