[프로그래머스 - lv3] 부대복귀

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/132266

프로그래머스

---

문제 풀이)

BFS를 이용해 해결할 수 있다.

발상을 뒤집어서 destination을 출발지점으로 선택해 역으로 탐색하면서 부대가 위치하 지점까지 도달할 수 있는지를 탐색하면 된다.

도달할 수 없는 경우도 있으므로 visit list를 -1로 초기화 시킨다. 이후 BFS를 수행하면 된다.

 

from collections import deque
def solution(n, roads, sources, destination):
    graph = [[] for _ in range(n + 1)]
    visit = [-1] * (n + 1)
    for x, y in roads:
        graph[x].append(y)
        graph[y].append(x)
    visit[destination] = 0
    q = deque([destination])
    while q:
        now = q.popleft()
        for next in graph[now]:
            if visit[next] == -1:
                visit[next] = visit[now] + 1
                q.append(next)
    return [visit[i] for i in sources]