문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/132266
문제 설명
강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다.
강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어진 sources의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간을 담은 배열을 return하는 solution 함수를 완성해주세요. 복귀가 불가능한 경우 해당 부대원의 최단시간은 -1입니다.
문제 해설
이 문제를 효율적으로 풀이하기 위해서는 DP의 Memoization 개념을 적절히 사용해야 한다. 포인트는 복귀하는 부대의 위치가 하나로 고정되어 있어 다른 부대에서 복귀 부대까지의 거리를 메모할 수 있다는 점이다.
이렇게 메모한 거리는 또 다른 부대에서 복귀 부대까지의 거리를 구할 때 재사용할 수 있다.
현재 부대에서 복귀 부대까지의 거리
= 현재 부대에서 중간부대까지의 거리 + 중간 부대에서 복귀부대까지의 거리
그리고 roads로 주어진 부대 간 연결된 간선을 계산하는 데 용이하도록 양방향으로 바꿔줄 필요가 있는데 아예 2차원 arraylist 형태로 만들어 버리면 access time을 줄일 수 있겠지만 공간복잡도가 극도로 커지게 되고 matrix를 구축하는 시간도 상당히 오래 걸리게 된다. 그래서 최종적으로 1차적으로는 arraylist 내부적으로는 linkedlist처럼 동작하는 방식을 사용하게 되었다.
어차피 어느 방식으로 만들든 순회해야 할 필요가 있기 때문에 시간적으로는 별로 차이나지 않는다.
마지막으로 BFS 방식으로 각 부대에서 복귀 부대까지의 최단 거리를 탐색해주기만 하면 된다.
BFS는 동일 가중치 간선에 대해서 최단 거리를 탐색하기 때문에 이후에 재탐색되는 경우가 있어도 갱신할 필요가 없다. 만약에 간선 간에 가중치가 다른 상황이었다면 다익스트라 알고리즘을 사용해야 했을 수 있다.
def solution(n , roads, sources, destination):
memo = [-1 for _ in range(n+1)]
memo[destination] = 0
map = [[] for _ in range(n+1)]
for a, b in roads:
map[a].append(b)
map[b].append(a)
queue = [destination]
while queue:
now = queue.pop(0)
for next in map[now]:
if memo[next] == -1:
queue.append(next)
memo[next] = memo[now] + 1
return [memo[source] for source in sources]