[프로그래머스,Java] Level3: 부대복귀

 

 

문제 분석:

 

목표 : 모든 강철 부대원이 복귀하는 최단 복귀시간

 

 

roads는 지나갈수있는 길

 

sources는 강철부대원이 현재 있는 지역

 

destination은 복귀해야하는 지점

 

문제를 읽어보니 그래프 문제다.

 

그래프 문제도 수많은 푸는 기법이 있다.  (최소 신장트리, 다익스트라, 플로이드 와샬..등등)

근데 이 문제는 다익스트라로 푸는게 바람직하다.

 

그 이유는 도착지가 동일하기 때문이다.

 

"각 병사가 도착지를 향해 가는것"을  반대로 생각하여,  "도착지에서 병사가 있는곳으로 간다"로

생각할수가 있기 때문입니다.

 

다익스트라는 그래프+DP 이기때문에, 써야하는 자료구조가 좀 많다.

 

 

문제 풀이:

 

 

먼저, 그래프를 표현 해줘야한다.

 

그래프를 표현해주는 방법은 다양하게 있지만, 필자는 Map으로 표현하였다.

 

Key:노드 , value:는  키 노드와 연결된 노드를 저장해 간선들이 저장된 Map을 표현했다.

 

이 문제 같은경우,  a,b의 대소차이를 모르기 때문에 양방향으로 넣어줬다.

 

 

다익스트라 DP의 시작이다.

 

visited는 노드의 방문을 체크하는 자료구조이며,

dp는 부대원의 이동거리 중복계산을 막는 용도이다.

 

만약,  노드마다 부여된 가중치가 모두 달랐다면,  2차원 방문체크배열로 , 간선마다 방문체크를 했을텐데

문제에서 모든 가중치가 1이므로  1차원 방문체크만 해도 좋다.

 

그 이유는, 만약 노드의 싸이클이 발동해도, 이미 먼저온 노드가 방문체크가 되었을것이며,

먼저온 노드가 나중에온 노드의 방문로직보다 무조건 최소거리가 짧다는걸 알 수 있기때문이다. 

 

 

 

만약 모든 간선의 가중치가 달랐다면,  visited의 배열과,

dp배열은 Math.min으로 최소값체크를 했을것이다.

 

하지만 가중치가 모두 1로 같으니 이렇게 짜도 된다.

 

이 과정이 모두 마무리 되었으면 부대원들의 최소거리를 출력하면 끝이다.

  

전체 풀이:

import java.util.*;
class Solution {
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = {};
        
        // 다이나믹 프로그래밍? => 다익스트라 
        // 출발점 1은 동일하게 출발 => 출발 ~ 모든정점 최소거리 
        
        // Map= 그래프 취급
        // Key:노드  value: key 노드와 연결된 노드들
        Map<Integer,List<Integer>> map = new HashMap<>();
        
        for(int[] road:roads){
            
            int a = road[0];
            int b= road[1];
                 
            //양방향의 길을 잡아줌
            List<Integer> a_list=map.getOrDefault(a,new ArrayList<>());
            a_list.add(b);
            map.put(a,a_list);
            
            List<Integer> b_list=map.getOrDefault(b,new ArrayList<>());
            b_list.add(a);
            map.put(b,b_list);
        }
        
        // 다익스트라 시작
        boolean[] visited= new boolean[n+1];
        int[] dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        
        // que에 담을것 노드 위치
        Queue<Integer> que = new LinkedList<>();
        visited[destination]=true;
        que.add(destination);
        
        dp[destination]=0;
        
        while(!que.isEmpty()){
            int p=que.poll();
           
            List<Integer> p_list= map.get(p);
            
            for(int temp:p_list){
                //양방향 방문체크
                if(!visited[temp]){
                    
                     visited[temp]=true;
                     dp[temp]=dp[p]+1;           
                     que.add(temp);
                }
               
            }
        }
      
        List<Integer> result = new ArrayList<>();
        for(int s:sources){
            if(dp[s]==Integer.MAX_VALUE){
                dp[s]=-1;
            }
            result.add(dp[s]);
        }
        
        answer=result.stream().mapToInt(i->i).toArray();
        
        return answer;
    }
}