깊이 우선 탐색은 그래프 탐색 알고리즘 중 하나로, 가능한 멀리까지 탐색을 진행한 후, 되돌아가며 탐색을 진행하는 방식입니다. 이 알고리즘을 배열을 사용하여 구현해보도록 하겠습니다.

1. 그래프 구현하기

먼저, 탐색할 그래프를 인접 리스트 방식으로 구현해야 합니다. 아래의 예제 코드를 참고하여 그래프를 구현합니다.

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B', 'E', 'F'],
    'E': ['C', 'D', 'G'],
    'F': ['D'],
    'G': ['E']
}

위의 예제에서는 graph라는 딕셔너리 자료형을 사용하여 그래프를 표현했습니다. 각 노드를 키로 사용하고, 해당 노드와 인접한 노드들의 리스트를 값으로 저장하였습니다.

2. 깊이 우선 탐색 구현하기

이제 그래프를 탐색하는 깊이 우선 탐색 알고리즘을 구현해보겠습니다. 아래의 예제 코드를 참고하여 구현합니다.

def dfs(graph, start_node):
    visited = []
    stack = [start_node]

    while stack:
        current_node = stack.pop()
        if current_node not in visited:
            visited.append(current_node)
            stack.extend(graph[current_node])

    return visited

위의 코드에서는 dfs라는 함수를 정의하였습니다. graph는 그래프를 나타내는 인접 리스트, start_node는 탐색을 시작할 노드를 의미합니다. visited는 방문한 노드를 저장하기 위한 리스트, stack은 탐색할 노드들을 저장하기 위한 스택입니다.

탐색은 스택이 빌 때까지 반복하며, 스택에서 현재 노드를 꺼내어 방문하지 않은 경우에만 방문 처리하고, 해당 노드와 인접한 노드들을 스택에 추가합니다.

탐색이 완료된 후에는 visited 리스트를 반환합니다.

3. 탐색 실행하기

위에서 구현한 깊이 우선 탐색 알고리즘을 실행해보겠습니다. 아래의 예제 코드를 참고하여 실행합니다.

result = dfs(graph, 'A')
print(result)  # ['A', 'C', 'E', 'G', 'D', 'F', 'B']

위의 코드에서는 graph는 앞서 정의한 그래프이고, 'A'를 시작 노드로 하여 탐색을 진행합니다. 결과는 ['A', 'C', 'E', 'G', 'D', 'F', 'B']와 같이 반환됩니다.

마무리

배열을 활용한 깊이 우선 탐색 구현 방법을 알아보았습니다. 이를 통해 그래프를 탐색하고, 경로를 찾는데 유용하게 활용할 수 있습니다. 코드를 이해하고 변형하여 원하는 그래프에 적용해보세요!

참고 자료:

• 깊이 우선 탐색(Wikipedia)
• 파이썬 공식 문서