[Python | 프로그래머스 | Lv_3] 부대복귀

😄 아이디어

1. 연결점을 저장한 각 노드 생성

2. 그래프 이동 시 시간 저장 배열 생성

3. BFS를 통한 탐색 ☝️최단 경로를 찾는 경우는 BFS 활용 명심

😄 코드

from collections import deque

global arr;

def bfs(graph, key):
    global arr
    visited[key] = 1
    
    q = deque([key])
    
    while q:
        x = q.popleft()
        for node in graph[x]:
            if arr[node] == -1:
                q.append(node)
                arr[node] = arr[x] + 1

def solution(n, roads, sources, destination):
    answer = []
    global arr
    arr = [-1] * (n + 1)
    arr[destination] = 0
    
    graph = {}
    
    for road in roads:
        val1 = graph.get(road[0], [])
        val1.append(road[1])
        graph[road[0]] = val1
        
        val2 = graph.get(road[1], [])
        val2.append(road[0])
        graph[road[1]] = val2
            
    bfs(graph, destination)
        
    for source in sources:
        answer.append(arr[source])
            
    return answer

✔️ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/132266