문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/132266

구현방법

도착지를 기준으로 생각해서 진행했습니다. -> 도착지 기준에서 뻣어나가면서 위치에 대한 거리를 체크해두면 sources 에 담긴 배열의 지역에도 갈 수 있겠다는 생각을 하고 선택했습니다.

ArrayList<>[] 에 각 위치에서 갈수 있는 곳을 전부 넣어두고

중복으로 가는 것을 막기위해서 중복체크를 진행

각 노드의 최소 거리를 넣어두기위해서 배열을 추가로 만들어뒀습니다. -> 배열의 각 값들은 -1로 초기화

다른분들의 풀이를 봤을때 다익스트라를 통해서도 가능하다는 것을 알았습니다.

구현알고리즘

BFS 알고리즘

CODE

package org.example.programers.부대복귀;

import java.util.*;
/**
 * 부대복귀
 * BFS 알고리즘 가능
 */
class Solution {

    List<Integer>[] road;
    int[] destinations;

    boolean[] visited;

    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = new int[sources.length];
        road = new ArrayList[n+1];
        destinations = new int[n+1];
        visited = new boolean[n+1];

        //-1로 채워두기
        Arrays.fill(destinations,-1);



        for(int idx =1;idx<=n;idx++){
            road[idx] = new ArrayList<>();
        }

        //연결된 도로들 적어두기
        for(int index = 0; index < roads.length;index++){
            int start = roads[index][0];
            int end = roads[index][1];

            road[start].add(end);
            road[end].add(start);
        }
        
        start(destination);
        for(int idx =0; idx <sources.length;idx++){
            answer[idx] = destinations[sources[idx]];
        }


        return answer;
    }

    private void start(int destination) {
        Queue<Integer> queue = new LinkedList<>();
        int cnt = 0;
        queue.offer(destination);
        queue.offer(cnt);
        visited[destination] = true;
        destinations[destination] = 0;

        while(!queue.isEmpty()){
            int cur = queue.poll();
            int node = queue.poll();
            //한번도 방문하지 않은경우 일단 갱신
            if(destinations[cur] == -1){
                destinations[cur] = node;
                //방문한적이있는경우 최소 거리인지 체크
            }else if(destinations[cur] != -1){
                destinations[cur] = Math.min(node,destinations[cur]);
            }

            for(int idx =0; idx <road[cur].size();idx++){
                int nxt_road = road[cur].get(idx);

                if(visited[nxt_road])
                    continue;

                visited[nxt_road] = true;
                queue.offer(nxt_road);
                queue.offer(node+1);
            }

        }


    }
}