문제링크

문제 링크

문제설명

제한사항

입출력예 및 설명

풀이

1. 각 sources에서 destination으로 가지말고, 문제 조건상 어차피 도착지는 단 하나니까 애초에 destination에서 출발하자
2. LinkedList를 자료형으로 가진 ArrayList를 선언하여서 각 지점간의 관계를 표현하고, destination에서의 최단거리를 기록할 int배열 (내 코드상 distance)도 하나 선언하자.
3. bfs를 돌면서, 각 distance가 최솟값이되면 갱신해주고, 아니면 continue!

코드

import java.util.*;
class Solution {
    static int[] distance; //destination에서부터 출발하여 각 지점마다 최소거리
    ArrayList<LinkedList<Integer>> chain;
    public void init(int n) {
        chain = new ArrayList<>(n + 1);
        for(int i = 0; i < n + 1; i++) 
        {
            chain.add(new LinkedList<>());
        }
        distance = new int[n + 1];
        Arrays.fill(distance, -1);        
    }
    public void bfs(LinkedList<Integer> start) {
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < start.size(); i++) 
        {
            q.add(start.get(i));
            distance[start.get(i)] = 1;
        }
        
        while(!q.isEmpty()) 
        {
            int now = q.poll();
            
            LinkedList<Integer> arr = chain.get(now);
            for(int i = 0; i < arr.size(); i++)
            {
                if(distance[arr.get(i)] == -1 || distance[arr.get(i)] > distance[now] + 1)
                {
                    q.add(arr.get(i));
                    distance[arr.get(i)] = distance[now] + 1;
                }
            }
        }
    }
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = new int[sources.length];
        init(n);
        for(int i = 0; i < roads.length; i++) 
        {
            chain.get(roads[i][0]).add(roads[i][1]);
            chain.get(roads[i][1]).add(roads[i][0]);
        }
        bfs(chain.get(destination));
        for(int i = 0; i < answer.length; i++)
        {
            answer[i] = distance[sources[i]];
            if(sources[i] == destination)
                answer[i] = 0;
        }
        return answer;
    }
}