Breadth First Search: Shortest Path

Problem Link
https://www.hackerrank.com/challenges/bfsshortreach/problem?isFullScreen=true

✅ Problem Summary

너비 우선 탐색(Breadth First Search)을 이용하여 특정 노드와 다른 노드와의 최단 거리를 구하는 문제

---

🧮 Applied Theory & Algorithm

1. 너비 우선 탐색 (Breadth-First Search)

그림 출처: Wikipedia

---

📑 My Answer

• 모든 테스트 케이스 통과

from collections import deque

def bfs(n, m, edges, s):
    graph = [set() for _ in range(n)]
    for u, v in edges:
        graph[u - 1].add(v - 1)
        graph[v - 1].add(u - 1)

    end_nodes = [i for i in range(n)]
    end_nodes.remove(s - 1)
    queue, result = deque([(s - 1, 0)]), [-1] * n
    while queue:
        temp, depth = queue.popleft()
        if temp in end_nodes:
            result[temp] = depth * 6
            end_nodes.remove(temp)
        for n in list(graph[temp]):
            queue.append((n, depth + 1))
            graph[temp].remove(n)
            graph[n].remove(temp)
    result.pop(s - 1)
    return result

📌 코드 구현 설명

• 정점 연결 정보가 저장되어 있는 edges를 가지고 graph를 만든다.
• 거리를 계산할 노드 번호를 저장할 end_nodes를 만든다.
  • 시작 노드는 제외시켜야 하므로 리스트 내장함수인 remove를 사용하여 시작 노드 번호를 리스트에서 제거한다.
• 탐색 결과를 저장할 queue와, 노드 간 최단 거리를 저장할 result를 선언한다.
• 반복문을 사용하여 그래프 내의 노드들을 BFS 방법으로 탐색한다.
  • 만나는 노드(temp)가 end_nodes에 있으면 result[temp]에 최단 거리인 depth를 저장하고(문제에서는 간선(edge) 하나의 길이가 6이라고 했으므로 6을 곱하여 저장), 해당 노드의 최단 거리를 구했으므로 end_nodes에서 지운다.
  • 노드 temp의 자식 노드들을 depth 정보와 함께queue에 저장하고, 해당 노드에 다시 방문하지 못하도록 graph에서 간선 정보를 지운다.
  • queue에 방문 정보가 더 이상 없을 때(조건에 맞는 모든 노드를 탐색한 상태)까지 반복한다.
• 탐색이 끝나면, result에서 시작 노드 s에 저장되어 있는 값을 지우고(시작 노드는 제외하고 출력해야함) return 한다.

---