[BFS,DP] - Lv3 - 부대복귀

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

프로그래머스

🌿 - 문제 설명

📌- 풀이

처음 문제를 보고 BFS로 풀면 되겠다 싶어서 BFS로 풀려다가 제한사항에 roads의 길이가 50만인 것을 보고 그냥 BFS로만 풀면 

모든 경우의 수를 계속 탐색하다보니 시간초과가 발생하기 때문에 BFS를 포함해서 DP를 사용해서 풀어야겠다고 생각했다.

 

 

 

1. 기본적으로 연결리스트로 양방향 그래프를 구현해서 각각 지역을 초기화

 

처음엔 sources순대로 [1,3,5]면 순차적으로 탐색하려했는데 이렇게 풀게되면 DP로 풀수 없게 되서 도착지부터 탐색하기로 했다.

 

 

위의 2번째 예시로 봤을 때 도착지부터 탐색을 하게 되면

 

1 - 2 , 4

2 - 1 , 4, 5

4 - 1, 5

5 - 2, 4

 

2 , 4 번을 먼저 탐색하고 visited에 5와의 거리 1 입력 -> 그리고 2번을 탐색하면서 인접한 1, 4, 5번이 다시 que에 들어갈 때 1번은 2에서 1번 더 진행됐으므로 visited[1] = 2.depth +1이고 ->  4와 5번은 이미 방문을 했기 때문에 더 최단 거리를 찾을 수 없으므로 생략

 

이렇게 que가 빌때까지 반복하게 되면 각각의 최단거리를 구할 수 있게 된다

🔥 - Java 전체 코드

 

import java.util.*;
class Solution {
    
    
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = new int[sources.length];
        int[] visited = new int[n+1];
        Arrays.fill(visited, Integer.MAX_VALUE);
        ArrayList<Integer>[] list = new ArrayList[n+1];
        
        for(int i =0;i<n+1;i++){
            list[i] = new ArrayList<Integer>();
        }
        
        for(int[] road : roads){ // 연결리스트로 초기화
            int road1 = road[0];
            int road2 = road[1];
            list[road1].add(road2);
            list[road2].add(road1);
        }
        
        
        Queue<Road> que = new LinkedList<>();
        que.add(new Road(destination,0));
        visited[destination] = 0;
        while(!que.isEmpty()){ // BFS로 도착지점부터 거꾸로 탐색
            Road a = que.poll();
            
            for(int i : list[a.x]){
                if(visited[i] == Integer.MAX_VALUE){
                    visited[i] = a.depth+1;
                    que.add(new Road(i,a.depth+1));
                }
            }
        }
        
        for(int i = 0;i<sources.length;i++){ // 시작지점마다 출력 visited[i]가 변경이 안되어있으면 오지 못한 곳이기 때문에 -1
            answer[i] = visited[sources[i]] == Integer.MAX_VALUE ? -1 : visited[sources[i]];
        }
        
        return answer;
    }
}

class Road{
    int x, depth;
    
    Road(int x, int depth){
        this.x = x;
        this.depth = depth;
    }
}