너비 우선 탐색(Breadth First Search, BFS)은 그래프에서 두 노드 사이의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 큐(Queue) 자료구조를 사용하여 구현할 수 있습니다. 이번 글에서는 배열을 활용하여 너비 우선 탐색을 구현하는 방법을 알아보겠습니다.

알고리즘 구현

1. 시작 노드를 큐에 넣고 방문한 노드로 표시합니다.
2. 큐가 비어있을 때까지 다음 과정을 반복합니다.
   1. 큐에서 노드를 하나 뺍니다.
   2. 해당 노드와 연결된 모든 미방문 노드를 큐에 넣고 방문한 노드로 표시합니다.
3. 탐색이 끝나면 방문한 노드의 순서대로 출력합니다.

아래는 배열을 활용한 너비 우선 탐색 알고리즘의 구현 예시입니다.

def bfs(graph, start):
    visited = []  # 방문한 노드를 저장하는 배열
    queue = [start]  # 탐색할 노드를 저장하는 큐

    while queue:
        node = queue.pop(0)  # 큐에서 노드 하나를 꺼냅니다.

        if node not in visited:
            visited.append(node)  # 방문한 노드로 표시합니다.

            for neighbor in graph[node]:
                queue.append(neighbor)  # 연결된 모든 미방문 노드를 큐에 넣습니다.

    return visited

사용 예시

다음은 사용자가 입력한 그래프에서 1을 시작 노드로 하는 너비 우선 탐색을 수행하는 예시입니다.

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [],
    4: [6],
    5: [6],
    6: []
}

start_node = 1
result = bfs(graph, start_node)
print(result)  # [1, 2, 3, 4, 5, 6]

결론

배열을 활용하여 너비 우선 탐색을 구현하는 방법을 알아봤습니다. 너비 우선 탐색은 그래프에서 최단 경로를 찾는 알고리즘으로, 배열과 큐 자료구조를 활용하여 구현할 수 있습니다. 이를 활용하면 다양한 문제에서 너비 우선 탐색을 활용할 수 있습니다.