[코딩 테스트 합격자 되기 파이썬 - 2주차]BFS

개념 문제

1. BFS(너비 우선 탐색) 알고리즘의 작동 원리를 설명하고, 어떤 자료구조를 사용하는지, 그리고 그 이유는 무엇인지 설명해주세요.
   BFS(너비 우선 탐색)는 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘입니다. 
   이를 위해 '큐' 자료구조를 채택하여 시작 노드를 큐에 넣은 다음, 방문 처리를 합니다. 이후,
   1. 큐가 비었는지 확인. 큐가 비었다면 방문할 수 있는 모든 노드를 방문했기 때문에 탐색을 종료합니다.
   2. 큐에서 노드를 팝합니다.
   3. 팝한 노드와 인접한 모든 노드를 확인하고 그 중 아직 방문하지 않은 노드는 큐에 푸시하여 방문처리
   이 과정을 반복하는 것이 BFS입니다.
   고려 사항으로는
   1. 현재 방문한 노드와 직접 연결된 모든 노드를 방문할 수 있어야 하고,
   2. 이미 방문한 노드인지 확인할 수 있어야 합니다.
   
   이러한 작업을 하기 위해서 큐의 특성에 대해서 알아야 합니다. 
   큐는 먼저 들어온 애들이 먼저 나가는 방식으로, 먼저 들어온 애들이 나중에 나가는 스택과는 반대의 개념입니다.
   큐의 특징을 활용하여 현재 노드와 인접한 모든 노드를 큐에 삽입하고, 먼저 들어간 순서대로 탐색을 이어나가는 방식입니다. 
   
   자세한 설명은 실전 문제 1. 너비 우선 탐색 순회에서 같이 보도록 하겠습니다.
2. BFS와 DFS(깊이 우선 탐색)의 차이점은 무엇이며, 각각 어떤 종류의 문제에 더 적합한지 예시를 들어 설명해주세요.
   DFS는 깊게 탐색 후 되돌아오는 특성이 있고, BFS는 가중치가 없는 그래프에서 최단 경로를 보장합니다.
   DFS는 가장 깊은 곳을 우선하여 탐색하고, 더 이상 탐색할 수 없으면 백트래킹하여 최근 방문한 노드부터 다시 탐색을 진행한다는 특징이 있어서 모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때나 그래프의 사이클을 감지해야 하는 경우 활용할 수 있습니다.
   BFS는 찾는 노드가 시작 노드로부터 최단 경로임을 보장합니다. 왜냐하면 시작 노드부터 직접 간선으로 연결된 모든 노드를 먼저 방문하기 때문입니다. 쉽게 말해 문제에 대한 답이 많은 경우, BFS는 이 답 중에서 가장 가까운 답을 찾을 때 유용합니다.
3. BFS 알고리즘의 시간 복잡도는 $O(V + E)$인데, 그래프의 형태(예 : 밀집 그래프 vs 희소 그래프)가 실제 수행 시간에 어떤 영향을 미칠 수 있을지 설명해주세요.
   이 부분에 대해서는 조금 더 공부하고 오도록 하겠습니다.

 

실전 문제

1. 너비 우선 탐색 순회(몸풀기 문제 37번)

from collections import deque

def bfs(graph, start) :
    print('시작 노드', start)
    q = deque()
    q.append(start)
    visited = []
    visited.append(start)

    while q :
        c = q.popleft()
        print('현재 노드', c)

        for nxt in graph.get(c, []) :
            if nxt not in visited :
                q.append(nxt)
                visited.append(nxt)
                print(f'현재 큐 상태 : {q}')
            else :
                print(f"{nxt}는 방문한 적이 있는 노드입니다.")

    return visited

def solution(graph, start) :
    adj_list = {}
    for u, v in graph :
        if u not in adj_list :
            adj_list[u] = [v]
        else :
            adj_list[u].append(v)
    # print(adj_list)
    return bfs(adj_list, start)

1번의 예제를 보면, 주어진 그래프를 인접 리스트로 변환하여보자. 

graph = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (4, 8), (5, 8), (6, 9), (7, 9)]
adj_list = {1: [2, 3], 2: [4, 5], 3: [6, 7], 4: [8], 5: [8], 6: [9], 7: [9]}

인접리스트를 가지고 BFS를 시도하여 보자.

1. deque()를 생성한다. deque는 Double Ended Queue 의 줄임말로, 양 끝에서 삽입이나 삭제를 할 수 있는 큐를 구현한 것이다. 양 끝에서 삽입이나 삭제를 할 수 있기 때문에 큐를 구현할 때 deque를 사용하는 것이 좋다.
2. 정답으로 visited 배열에 차례대로 append 하여 최종적으로 정답으로 return 한다.
   1. 만약 중간에 방문한 적이 있는 노드가 있다면, 무시하고 진행한다. 

사실 책에서는 defaultdict로 인접리스트를 구현해놓았는데, 혹시나 라이브러리를 못쓰는 상황이 올 수도 있기 때문에 딕셔너리를 활용하여 구현하였고, visited 배열은 set으로 하게 될 경우, 접근 속도가 더 빠르나, 굳이 result 배열도 같이 만들어야 하나 싶어서 생략하는 방법으로 구현해보았다. 

정답이 어떤식으로 흘러가는지 확인해보자. 

시작 노드 1
    현재 노드 : 1
    현재 큐 상태 : deque([2])
    현재 큐 상태 : deque([2, 3])
    현재 노드 : 2
    현재 큐 상태 : deque([3, 4])
    현재 큐 상태 : deque([3, 4, 5])
    현재 노드 : 3
    현재 큐 상태 : deque([4, 5, 6])
    현재 큐 상태 : deque([4, 5, 6, 7])
    현재 노드 : 4
    현재 큐 상태 : deque([5, 6, 7, 8])
    현재 노드 : 5
    8는 방문한 적이 있는 노드입니다.
    현재 노드 : 6
    현재 큐 상태 : deque([7, 8, 9])
    현재 노드 : 7
    9는 방문한 적이 있는 노드입니다.
    현재 노드 : 8
    현재 노드 : 9
[1, 2, 3, 4, 5, 6, 7, 8, 9]

2. 게임 맵 최단거리

프로그래머스

 

3. 경주로 건설

프로그래머스