[level 3] 부대복귀 - 132266

문제 링크

성능 요약

메모리: 135 MB, 시간: 773.04 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

문제 설명

강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다.

강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어진 sources의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간을 담은 배열을 return하는 solution 함수를 완성해주세요. 복귀가 불가능한 경우 해당 부대원의 최단시간은 -1입니다.

제한사항

• 3 ≤ n ≤ 100,000
  • 각 지역은 정수 1부터 n까지의 번호로 구분됩니다.
• 2 ≤ roads의 길이 ≤ 500,000
  • roads의 원소의 길이 = 2
  • roads의 원소는 [a, b] 형태로 두 지역 a, b가 서로 왕복할 수 있음을 의미합니다.(1 ≤ a, b ≤ n, a ≠ b)
  • 동일한 정보가 중복해서 주어지지 않습니다.
    • 동일한 [a, b]가 중복해서 주어지지 않습니다.
    • [a, b]가 있다면 [b, a]는 주어지지 않습니다.
• 1 ≤ sources의 길이 ≤ 500
  • 1 ≤ sources[i] ≤ n
• 1 ≤ destination ≤ n

---

입출력 예

---

입출력 예 설명

입출력 예 #1

• 지역 2는 지역 1과 길로 연결되어 있기 때문에, 지역 2에서 지역 1의 최단거리는 1입니다.
• 지역 3에서 지역 1로 이동할 수 있는 최단경로는 지역 3 → 지역 2 → 지역 1 순으로 이동하는 것이기 때문에, 지역 3에서 지역 1의 최단거리는 2입니다.
• 따라서 [1, 2]를 return합니다.

입출력 예 #2

• 지역 1에서 지역 5의 최단경로는 지역 1 → 지역 2 → 지역 5 또는 지역 1 → 지역 4 → 지역 5 순으로 이동하는 것이기 때문에, 최단거리는 2입니다.
• 지역 3에서 지역 5로 가는 경로가 없기 때문에, 지역 3에서 지역 5로 가는 최단거리는 -1입니다.
• 지역 5에서 지역 5는 이동할 필요가 없기 때문에, 최단거리는 0입니다.
• 따라서 [2, -1, 0]을 return합니다.

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

---

문제 풀이

문제 분석

이 문제는 여러 부대원들이 흩어져 있는 위치(sources)에서 강철부대 본부(destination)로 복귀하는 최단 시간을 계산하는 문제입니다.

• 입력:
  • n: 총 지역의 수 (노드의 개수).
  • roads: 두 지역을 연결하는 길 정보 (양방향 간선, 가중치 1).
  • sources: 최단 시간을 구해야 하는 출발 지역 목록.
  • destination: 목표 도착 지역 (부대).
• 제약 조건: 두 지역 간 길을 통과하는 시간은 모두 1로 동일합니다 (가중치 1인 그래프).
• 출력: sources에 주어진 순서대로 각 지역에서 destination까지의 최단 시간을 담은 배열을 반환합니다. 복귀 불가능 시 -1을 반환합니다.

접근 방법

이 문제는 가중치가 1인 그래프에서 최단 거리를 찾는 전형적인 최단 경로 문제입니다.

1. 알고리즘 선택: 가중치가 모두 1인 최단 경로 문제에서는 다익스트라 알고리즘보다 훨씬 효율적인 **너비 우선 탐색(Breadth-First Search, BFS)**을 사용하는 것이 가장 적합합니다. BFS는 시작점에서부터 거리를 층별로 탐색하며 최단 거리를 보장합니다.

2. 효율적인 탐색 전략 (핵심):

   • sources의 크기는 최대 500개입니다. 만약 각 source마다 destination까지의 최단 거리를 구하기 위해 BFS를 개별적으로 실행한다면 최대 500번의 탐색을 해야 합니다.
   • 하지만 이 그래프는 양방향(왕복 가능)이므로, 지역 A에서 B까지의 최단 거리는 B에서 A까지의 최단 거리와 같습니다.
   • 따라서, sources에서 destination으로 가는 경로를 찾는 대신, destination을 시작점으로 단 한 번의 BFS를 실행하여 모든 지역까지의 최단 거리를 한 번에 계산합니다. 이 결과를 이용하여 각 source의 최단 거리를 즉시 찾아낼 수 있습니다.

구현 설명

1. 인접 리스트를 사용한 그래프 구성

• 먼저 n개의 지역을 표현하는 인접 리스트(adjacency list, graph)를 0부터 $n-1$까지의 인덱스로 초기화합니다.
• 입력 데이터는 1-기반 인덱싱(지역 1부터 $n$)을 사용하므로, 코드에서 이를 0-기반 인덱싱으로 변환하여 사용합니다 (x, y = i[0]-1, i[1]-1).
• roads 배열을 순회하면서 양방향 간선을 graph에 추가합니다. ([a, b]가 주어지면, graph[a-1]에 b-1을, graph[b-1]에 a-1을 추가).

2. BFS를 통한 최단 거리 배열 계산

• BFS(graph, dest) 함수를 호출하여 최단 거리를 계산합니다. 이때 시작점 dest는 destination-1입니다.
• dist 배열을 $n$ 크기로 초기화하며, 모든 값을 -1로 설정합니다. -1은 해당 지역에 도달할 수 없음을 의미합니다.
• 시작점(dest)의 거리는 0으로 설정하고, 탐색을 위한 큐(stack, deque 사용)에 시작점을 넣습니다.
• 큐가 빌 때까지 다음 작업을 반복합니다.
  • 현재 노드 x를 큐에서 꺼냅니다.
  • x와 연결된 모든 이웃 노드 i를 확인합니다.
  • 만약 이웃 노드 i의 dist[i]가 아직 -1이라면 (즉, 아직 방문하지 않았다면):
    • dist[i]를 dist[x] + 1로 업데이트하고 (최단 거리 갱신), i를 큐에 넣습니다.
• 탐색이 완료되면, dist 배열에는 destination에서부터 모든 지역까지의 최단 거리가 저장됩니다.

3. 결과 반환

• 메인 solution 함수는 sources 배열을 순회합니다.
• 각 출발지 i에 대해, BFS 결과 배열 arr에서 해당 지역의 최단 거리를 조회합니다 (arr[i-1]).
• 조회된 값을 최종 answer 배열에 순서대로 추가하여 반환합니다. 만약 복귀 불가능한 지역이라면 arr[i-1]은 -1일 것이므로, 그대로 결과에 반영됩니다.

⏱복잡도 분석

• $N$: 지역의 수 (노드 수, 최대 100,000)
• $M$: 도로의 수 (간선 수, 최대 500,000)
• $S$: 출발지(sources)의 수 (최대 500)

시간 복잡도:

1. 그래프 구성: 모든 도로 정보를 읽고 인접 리스트를 구축하는 데 $O(M)$ 시간이 소요됩니다.
2. BFS 실행: BFS는 인접 리스트를 사용할 경우 모든 노드 $V$와 모든 간선 $E$를 한 번씩 방문하므로 $O(V + E)$의 시간이 걸립니다. 여기서는 $O(N + M)$입니다.
3. 결과 취합: sources 배열을 순회하며 결과를 찾는 데 $O(S)$ 시간이 소요됩니다.

총 시간 복잡도는 $O(M + N + S)$입니다. $N$과 $M$이 $S$보다 훨씬 크므로, 전체적으로 **$O(N + M)$**의 매우 효율적인 성능을 가집니다.

공간 복잡도:

1. graph: 인접 리스트를 저장하는 데 $O(N + M)$ 공간이 필요합니다.
2. dist: 거리를 저장하는 배열로 $O(N)$ 공간이 필요합니다.
3. stack (큐): 최악의 경우 모든 노드를 저장할 수 있으므로 $O(N)$ 공간이 필요합니다.

총 공간 복잡도는 **$O(N + M)$**입니다.

핵심 포인트

1. BFS 사용: 모든 간선의 가중치가 1이므로, 최단 경로를 구하기 위해 너비 우선 탐색(BFS)을 사용하는 것이 가장 효율적입니다.
2. 역방향 단일 탐색 (핵심 최적화): 여러 출발지(sources)에서 하나의 목적지(destination)로 가는 최단 경로를 구해야 하지만, 그래프가 양방향이므로, 목적지(destination)에서 출발하여 모든 노드까지의 최단 거리를 단 한 번의 BFS로 계산합니다.
3. 인덱싱 처리: 문제에서 주어진 1-기반 지역 번호(1 ~ N)를 Python 리스트에 맞게 0-기반 인덱스(0 ~ N-1)로 정확하게 변환하여 사용하는 것이 중요합니다.

풀이 코드

from collections import deque

def solution(n, roads, sources, destination):
    answer = []
    graph = [[] for i in range(n)]
    for i in roads:
        x,y = i[0]-1,i[1]-1
        graph[x].append(y)
        graph[y].append(x)
    
    arr=BFS(graph,destination-1)
    answer=[]
    for i in sources:
        answer.append(arr[i-1])
        
    return answer

def BFS(graph, dest):
    stack = deque([dest])
    dist = [-1 for i in range(len(graph))]
    dist[dest] = 0
    while stack:
        x = stack.popleft()
        for i in graph[x]:
            if dist[i] == -1:
                dist[i] = dist[x]+1
                stack.append(i)
                
    return dist