넓이 우선 순회(breadth first traversal) 에서의 큐(Queue) 사용에서 알 수 있는 여러 자료구조의 활용

넓이 우선 순회(Breadth First Traversal)

 

넓이 우선 순회(Breadth First Traversal)는 트리 또는 그래프를 순회하는 방법 중 하나로, 루트 노드에서 시작하여 인접한 노드들을 먼저 탐색하는 방식입니다. 이를 위해서 큐(Queue) 자료구조를 사용하여 먼저 방문한 노드를 먼저 처리하는 것이 일반적입니다.

 

넓이 우선 순회에서 큐 자료구조를 사용하는 방법 외에도, 다양한 자료구조들을 활용할 수 있습니다. 이번에는 넓이 우선 순회에서 사용되는 다양한 자료구조들을 살펴보도록 하겠습니다.

1. 큐(Queue)

가장 일반적으로 사용되는 자료구조로, 먼저 방문한 노드를 먼저 처리하기 위해 사용됩니다. 노드를 큐에 삽입하는 방법으로 넓이 우선 순회를 수행합니다.

 

2. 스택(Stack)

큐와 반대로, 나중에 방문한 노드를 먼저 처리하기 위해 사용됩니다. 스택에 노드를 삽입하는 방법으로 넓이 우선 순회를 수행할 수 있습니다. 하지만, 이 방법은 일반적으로 잘 사용되지 않습니다.

 

3. 덱(Deque)

덱은 양방향에서 삽입과 삭제가 가능한 자료구조입니다. 큐와 스택의 장점을 모두 가지고 있기 때문에, 넓이 우선 순회에서도 사용됩니다.

 

4. 우선순위 큐(Priority Queue)

우선순위 큐는 큐의 삽입과 삭제 시 우선순위에 따라 처리하는 자료구조입니다. 넓이 우선 순회에서도 노드의 우선순위에 따라 큐에 삽입할 수 있으며, 이 방법은 최소 신장 트리(Minimum Spanning Tree) 알고리즘 등에서 사용됩니다.

 

5. 연결 리스트(Linked List)

연결 리스트는 노드와 링크(포인터)로 이루어진 자료구조입니다. 넓이 우선 순회에서는 각 노드에 방문한 순서를 저장하고, 다음 노드로 이동하기 위한 링크를 가지고 있습니다.

 

6. 배열(Array)

배열은 노드를 일렬로 저장하는 자료구조입니다. 넓이 우선 순회에서는 각 노드의 인덱스를 이용하여 노드를 방문한 순서를 저장합니다. 하지만, 배열은 노드의 삽입 및 삭제 연산이 불가능하므로, 트리의 구조가 바뀌는 경우에는 사용할 수 없습니다.

 

7. 힙(Heap)

힙은 부모 노드와 자식 노드 간의 대소 관계가 정해진 완전 이진 트리입니다. 넓이 우선 순회에서는 노드의 값을 우선순위로 사용하여, 우선순위가 높은 노드부터 큐에 삽입합니다. 이를 위해, 최대 힙 또는 최소 힙을 사용합니다

 

8. 해시 테이블(Hash Table)

해시 테이블은 키-값 쌍으로 데이터를 저장하는 자료구조입니다. 넓이 우선 순회에서는 각 노드에 해시 함수를 적용하여 인덱스를 구하고, 해당 인덱스에 노드를 저장합니다. 하지만, 해시 함수의 충돌 문제와 순서를 보장하지 않는다는 단점이 있습니다.

위와 같이 넓이 우선 순회에서는 큐 외에도 다양한 자료구조들을 활용할 수 있습니다. 각 자료구조의 특징과 장단점을 고려하여, 특정 상황에서 가장 적합한 자료구조를 선택하여 사용할 수 있습니다.

 

왜 큐를 쓰는가?

 

넓이 우선 순회(Breadth First Traversal)에서 큐(Queue)를 사용하는 것의 주요 장점은 다음과 같습니다.

 

1. 먼저 방문한 노드를 먼저 처리

큐는 먼저 들어온 데이터를 먼저 처리하는 FIFO(First In First Out) 방식을 사용하기 때문에, 먼저 방문한 노드를 먼저 처리할 수 있습니다. 이는 넓이 우선 순회에서 루트 노드에서부터 시작하여 인접한 노드들을 먼저 방문해야 하는 상황에서 매우 유용합니다.

 

2. 구현이 간단

큐는 구현이 간단하고, 사용이 쉽습니다. 또한, 파이썬에서는 deque 모듈을 사용하여 큐를 구현할 수 있습니다.

 

3. 메모리 사용량이 적음

큐는 넓이 우선 순회에서 방문한 노드들을 저장할 때, 해당 노드의 인접한 노드들을 먼저 저장하고 처리하므로, 메모리 사용량이 적습니다. 따라서, 트리나 그래프가 매우 큰 경우에도 사용할 수 있습니다.

 

4.최단 경로 문제에 적합

넓이 우선 순회는 최단 경로 문제(shortest path problem)에서 매우 적합한 방법입니다. 이는, 루트 노드에서부터 시작하여, 인접한 노드들을 먼저 방문하므로, 루트 노드와의 거리가 가까운 노드들부터 처리되기 때문입니다.

 

5. 그래프 탐색에 적합

큐를 사용한 넓이 우선 순회는 그래프 탐색에 적합합니다. 이는, 인접한 노드들을 먼저 방문하므로, 그래프의 모든 노드를 방문할 수 있습니다. 또한, 그래프에서 사이클이 있는 경우에도 사용할 수 있습니다.

따라서, 넓이 우선 순회에서 큐를 사용하는 것은, 먼저 방문한 노드를 먼저 처리하고, 구현이 간단하며, 메모리 사용량이 적고, 최단 경로 문제에 적합하며, 그래프 탐색에 적합하다는 장점이 있습니다.

 

 

무엇보다도 큐를 활용할 경우 탐색 알고리즘의 방향을 바꿀 수 있다는 점이 주된 포인트라고 할 수 있겠습니다.