<aside> 💬 lv2, 데이터 구조, 너비 우선 탐색(BFS)

그래프의 최단 경로 찾기

문제 설명

주어진 무방향 그래프에서 두 노드 간의 최단 경로의 길이를 계산하는 함수를 작성해주세요. 그래프는 딕셔너리 형태로 표현되며, 키는 노드를 나타내고 값은 해당 노드에 직접 연결된 이웃 노드들의 리스트입니다.

예를 들어, 노드 0과 노드 3 간의 최단 경로를 찾는 경우, 그래프가 {"0": ["1", "2"], "1": ["0", "3"], "2": ["0"], "3": ["1"]}로 주어진다면, 최단 경로의 길이는 2입니다 (0 -> 1 -> 3).

제한 사항

노드의 수는 1 이상 100 이하입니다.
각 노드는 0부터 시작하는 정수로 표현됩니다.
노드 간에는 여러 경로가 존재할 수 있지만, 무방향 그래프에서는 양방향으로만 이동 가능합니다.
시작 노드와 목표 노드는 주어진 그래프 내에 반드시 존재합니다.

입출력 예

입력 (그래프, 시작 노드, 목표 노드)	출력 (최단 경로 길이)
{"0": ["1", "2"], "1": ["0", "3"], "2": ["0"], "3": ["1"]}, "0", "3"	2
{"0": ["1"], "1": ["0", "2"], "2": ["1"]}, "0", "2"	2
{"0": ["1"], "1": ["0"]}, "0", "1"	1

입출력 설명

주어진 그래프에서 시작 노드와 목표 노드 간의 최단 경로의 길이를 계산하여 반환합니다.

</aside>

😺 풀이 1. BFS 알고리즘 이용

from collections import deque **#1 deque 사용**

def solution(data):
    def bfs_shortest_path(graph, start, end): **#2 solution 함수 내부에 bfs_shortest_path 함수를 정의**
        visited = set() **#3 변수 준비**
        queue = deque([(start, 0)]) 

        while queue: **#4 BFS 수행하기 위해 반복**
            current, distance = queue.popleft()
            if current == end:
                return distance

            if current not in visited: **#5 현재 노드가 이전에 방문하지 않은 노드라면**
                visited.add(current)
                for neighbor in graph.get(current, []):
                    queue.append((neighbor, distance + 1))

        return -1 **#6 bfs_shortest_path 함수 종료**   

    graph = data["graph"] **#7 최종**
    start = data["start"]
    end = data["end"]
    return bfs_shortest_path(graph, start, end)

단계별 풀이 전략

deque 사용

deque 모듈을 가져옵니다. deque는 양쪽 끝에서 빠른 삽입과 삭제를 지원하는 큐(queue) 자료구조입니다.
solution 함수 내부에 bfs_shortest_path 함수를 정의

이 함수는 그래프 graph, 시작 노드 start, 끝 노드 end를 매개변수로 받습니다.
변수 준비

visited는 방문한 노드를 저장하는 세트(set)입니다. queue는 deque를 사용하여 초기화됩니다. 초기에는 시작 노드와 거리 0의 튜플 (start, 0)을 포함합니다.
BFS 수행하기 위해 반복

BFS(너비 우선 탐색)를 수행하기 위해 queue가 비어있지 않은 동안 반복합니다. 큐에서 현재 노드 current와 해당 노드까지의 거리 distance를 꺼냅니다. 현재 노드가 끝 노드 end와 같다면 최단 경로의 길이 distance를 반환합니다.
현재 노드가 이전에 방문하지 않은 노드라면

현재 노드를 visited 세트에 추가하여 방문 표시를 합니다. 현재 노드의 이웃 노드 들을 반복합니다. graph.get(current, [])를 사용하여 현재 노드의 이웃 노드 들을 가져옵니다. 이웃 노드가 없는 경우 빈 리스트 []를 반환합니다. 각 이웃 노드와 현재 노드까지의 거리에 1을 더한 값의 튜플 (neighbor, distance + 1)을 큐에 추가합니다.
bfs_shortest_path 함수 종료

BFS가 끝났는데도 끝 노드를 찾지 못한 경우 -1을 반환하여 경로가 없음을 나타냅니다.
최종

입력 데이터 data에서 그래프 graph, 시작 노드 start, 끝 노드 end를 가져옵니다. bfs_shortest_path 함수를 호출하여 최단 경로의 길이를 계산하고 반환합니다.

이 코드는 BFS 알고리즘을 사용하여 그래프에서 시작 노드와 끝 노드 사이의 최단 경로의 길이를 찾는 코드입니다. 큐를 사용하여 BFS를 수행하며, 방문한 노드를 추적하여 중복 방문을 방지합니다. 최단 경로를 찾으면 해당 경로의 길이를 반환하고, 경로가 없는 경우 -1을 반환합니다.

알아 둬야 할 개념

이 풀이 방법의 핵심은 너비 우선 탐색(Breadth-First Search, BFS) 알고리즘의 이해 입니다. 너비 우선 탐색(BFS, Breadth-First Search)은 그래프나 트리 구조에서 노드를 탐색하는 알고리즘 중 하나 입니다. BFS는 시작 노드에서 시작하여 인접한 노드를 먼저 탐색하고, 그 다음 단계로 이동하여 탐색을 진행합니다. 즉, 같은 레벨에 있는 노드 들을 먼저 탐색한 후, 다음 레벨로 넘어가는 방식입니다.

BFS의 동작 원리

시작 노드를 큐(Queue)에 삽입하고 방문했다는 표시를 합니다.
큐가 빌 때까지 다음 단계를 반복합니다.
- 큐에서 노드를 하나 꺼냅니다.
- 꺼낸 노드의 인접한 노드 들 중 아직 방문하지 않은 노드 들을 큐에 삽입하고 방문했다는 표시를 합니다.

BFS는 큐를 사용하여 노드를 저장하고 방문 순서를 관리합니다. 큐에 삽입된 노드는 먼저 삽입된 순서대로 탐색 되므로, 같은 레벨에 있는 노드 들을 먼저 탐색하게 됩니다. BFS는 최단 경로 문제, 연결된 컴포넌트 찾기, 이분 그래프 판별 등 다양한 문제에 활용됩니다. BFS의 시간 복잡도는 O(V + E)이며, V는 노드의 개수, E는 간선의 개수를 나타냅니다.

다음은 BFS의 간단한 예시 코드입니다.