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

문제 설명

강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 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

 

정답 설명

문제에서 가장 핵심이 되는 것이 바로 지역이다. 지역들은 서로 연결성을 가지고 있고, 우리는 연결된 지역들을 탐색하며 해당 지역부터 목적지까지의 거리를 구해야 한다.

이 문제를 조금 더 단순화 하면, 결국 여러개의 노드로 이루어 진 그래프를 탐색하는 문제이다. 

 

그래프 내부에서 서로간의 최단 경로를 구하는 것은 조건에 따라 조금씩 다른 방법들이 존재한다.

이번 문제는 그래프 내부의 모든 노드 에서 하나의 목적지 노드 까지의 거리를 구하는 것이 목표이고, 이는 BFS로 쉽게 구현할 수 있다.

 

그래프를 구성하는 노드들 중 목적지와 바로 인접한 노드들을 생각해 보자. 이 노드들이 목적지 노드까지 거쳐야 하는 경로의 수는 1개 이다. 

그렇다면, 방금 봤던, 목적지 노드와 바로 인접한 노드들과 연결된 다른 노드들은 어떨까? 해당 노드들은 목적지까지 거쳐야 하는 경로의 수가 2개 이다. 이 2라는 수는 목적지로 향하는 경로에 있는 노드의 경로 수 + 1 로 계산할 수 있다.

목적지와 한 칸씩 멀어질 수록, 목적지로 향하는 경로의 비용은 1 증가한다.

이는, 목적지부터 시작해서, 인접한 모든 노드의 목적지까지의 비용을 자신의 비용 + 1로 업데이트 하는 방법으로 구현될 수 있습니다.

 

Queue를 이용해 BFS를 구현하여 문제를 해결해 보자.

소스 코드

import java.util.*;
class Solution {
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = new int[sources.length];
        Region[] regions = new Region[n];
        Queue<Region> queue = new LinkedList<>();
        
        for(int i = 0; i<n; i++){
            regions[i] = new Region(i+1);
        }
        
        for(int[] road : roads){
            int a = road[0] - 1;
            int b = road[1] - 1;
            
            regions[a].addNeighbor(regions[b]);
            regions[b].addNeighbor(regions[a]);
        }
        
        regions[destination-1].cost = 0;
        queue.add(regions[destination-1]);
        while(!queue.isEmpty()){
            Region r = queue.poll();
            Iterator<Region> iter = r.neighbor.iterator();
            while(iter.hasNext()){
                Region neighbor = iter.next();
                if(neighbor.cost != -1)
                    continue;
                neighbor.cost = r.cost + 1;
                queue.add(neighbor);
            }
        }
        
        for(int i = 0; i<sources.length; i++){
            answer[i] = regions[sources[i]-1].cost;
        }
        
        return answer;
    }
}
class Region{
    int cost = 0;
    int index;
    List<Region> neighbor;
    
    public Region(int index){
        this.index = index;
        neighbor = new LinkedList<>();
        this.cost = -1;
    } 
    
    public void addNeighbor(Region n){
        neighbor.add(n);
    }
}