TIL - BFS 너비 우선 탐색

문제

- BFS로 그래프를 탐색합니다.
- 가까운 정점부터 방문합니다.
- 큐(Queue)를 사용합니다.

 

 

 

문제풀이

from collections import deque

# 시작점과 동일한 레벨인지는 어떻게 판단하지? 
def bfs(graph, start):
    """
    너비 우선 탐색
    
    Args:
        graph: 그래프 딕셔너리
        start: 시작 정점
    
    Returns:
        방문 순서 리스트
    """
    visited = []
    
    # TODO: 큐 생성 및 시작 정점 추가
    ## 방문한 정점 집합
    queue = list()
    # 시작 정점 추가
    queue.append(start)
    
    arr = []
    
    # 큐가 빌때까지
    while queue:
        # 가장 앞 큐 뽑기 [시작점 뽑기]
        current = queue.pop(0)
        visited.append(current) # [방문점에 추가]
        
        # 인접한 정점 확인 [다음에 갈 정점을 확인하기 위해]
        for i in graph[current]:
            # 큐가 방문하지 않고 & 큐에도 없을 때 [다음 방문할 곳 추가하기 위해]
            if i not in visited and i not in queue:
                queue.append(i)
    
    return visited

 

 

 

너비 우선 탐색

너비 우선 탐색은 횡의 방향으로 갖는 완전탐색이다. 큐를 이용해서 FIFO(First in First Out)의 방식을 사용한다.

1. 시작 노드를 큐에 저장하고, 맨 앞의 값을 꺼낸다.
2. 문제에서 요구하는 연산을 수행하고 
3. 인접 노드를 큐에 저장
4. 탐색이 끝난 노드를 버린다.
5. 큐가 빌 때까지 반복

 

 

 

 

어려웠던 점

1. 시작점과 동일한 레벨인지는 어떻게 판단할지?
   • 처음에 너비 우선 탐색을 검색했을 때 동일한 레벨의 것부터 탐색한다고 봤었다. 그래서 이 동일한 레벨인지에 대해 어떻게 판단하는 지? 에 대해 혼란스러웠다. 
   • 동료학습을 통해 이에 대해 이야기해봤는데, 0이 시작노드일 때 이와 인접한 노드들이 그와 비슷하거나 바로 하위 레벨일 것이다. 인접 노드들 먼저 돈 후에 하위 노드로 내려가는 로직이기 때문에 동일한 레벨인지 판단하는 것은 필요하지 않을 것이라는 결론이 나왔다. → 몇 레벨인지 확인하려면 별도 추적 필요 

 

    graph = {
        0: [1, 2],
        1: [0, 2],
        2: [0, 1, 3],
        3: [2]
    }

 

 

2. queue = list() 를 사용하니 내부적으로 배열로 저장되어 있어 pop(0) 을 하면 시간복잡도가 O(n)이다.

• list 는 배열 (연속된 메모리 블록) 으로 저장되어 있다.
• 맨 앞 요소를 뺐을 때 나머지가 다 한 칸씩 이동해야한다.
  • 좀 더 효율적으로 변경하려면 list 는 collections.deque 를 사용하고 → pop 이 O(1)
  • visited 는 set 을 사용하면 된다. → in 조회 시 O(1)

 

    visited = set()
    
    queue = deque()
    queue.append(start)
    
    arr = []

    while queue :
        current = queue.popleft()
        
        for i in graph[current]:
            if i not in visited and i not in queue :
                queue.append(i)
                visited.add(i)
    return list(visited)