title: "[프로그래머스] 부대복귀 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/132266"
description: "프로그래머스 Level 3 문제 [부대복귀]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

from collections import defaultdict, deque

D = [-1] * 100001
vis = [False] * 100001
def bfs(s, A):
    q = deque()
    
    D[s] = 0
    vis[s] = True
    q.append((s, 0))
    
    while len(q) != 0:
        u, d = q.popleft()
        for v in A[u]:
            if not vis[v]:
                D[v] = d+1
                vis[v] = True
                q.append((v, d+1))

def solution(n, roads, sources, destination):
    # destination로부터 시작해서 bfs를 돌려서 depth를 구합니다.
    A = defaultdict(list)
    for u, v in roads:
        A[u].append(v)
        A[v].append(u)
        
    bfs(destination, A)
    
    answer = [D[s] for s in sources]
    return answer

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges