[Algorithm] programmers-132266-부대복귀

/*
1. 각 source에 대해 result를 구해야한다
2. 모든가중치가 1이니 우선BFS로 풀어보고 안되면 다익스트라로.
*/
class Solution {
    static ArrayList<ArrayList<Integer>> roadList = new ArrayList<>();
    static int N;
    static int target;
    static int[] dist;

    public int[] solution(int n, int[][] roads,int[] sources, int destination) {
        dist = new int[n+1];
        Arrays.fill(dist,-1);
        int[] answer = new int[sources.length];
        N = n;
        target = destination;
        //map크기만큼 arrayList만들기
        for(int i=0;i<=n;i++){
            roadList.add(new ArrayList<>());
        }

        //각road저장
        for(int i=0;i<roads.length;i++){
            int from = roads[i][0];
            int to = roads[i][1];
            roadList.get(from).add(to);
            roadList.get(to).add(from);
        }

        bfs(destination);

        for(int i=0;i<sources.length;i++)
            answer[i] = dist[sources[i]];


        return answer;
    }

    static void bfs(int start){
        boolean[] visited = new boolean[N+1];
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        int level = 0;
        visited[start] = true; //방문처리

        while(!q.isEmpty()){
            int size = q.size();
            for(int reps=0 ; reps<size ; reps++){
                int source = q.poll();
                dist[source] = level;

                ArrayList<Integer> list = roadList.get(source); //해당 노드와 연결된 길 탐색
                for(int i=0;i<list.size();i++){
                    int next = list.get(i);
                    if(!visited[next]){
                        visited[next] = true; //방문처리
                        q.offer(next);
                    }
                }
            }
            level++;
        }
    }
}

• 가중치가 1일때에는 BFS로도 풀이가 가능하다. 해보고 혹시 안되면 다익스트라로 풀어보려고했다.

• 핵심은 각 source의 원소마다 bfs를 매번 호출하는 것이 아니라 destination에서 각 노드까지의 거리를 한번만 구하고 이를 dist배열에 기록한뒤 풀어야 시간초과가 안난다. source[i] -> destination을 각 source마다 구하지 말고 destination -> source[i]를 구하는 함수 한번만 호출한 뒤 답 출력!

• BFS를 할때 level을 선언해서 깊이가 1씩 깊어질때마다 증가시켜줬다. 이렇게 하면 몇개의 노드를 거쳤는지 알 수 있다.

• 또한 큐에서 꺼낼 때 방문체크를 했는데 그러면 큐에 중복된 노드가 들어가고 잘못된 거리가 들어갈 수 있다. 따라서 offer()하기 전에 미리 방문체크를 해줘야한다.

• 마찬가지로 별거 아니긴 한데 size변수를 따로 할당해서 for(int reps=0 ; reps<size ; reps++) 라는 구문을 만들지 않고 for(int reps=0; reps<q.size() ; reps++) 로 해버리면 큐의 사이즈가 수시로 변해서 level을 정확히 구할 수 없다.

• 추가로 2차원 배열이 아니라 2차원 ArrayList를 써서 존재하는 길만 표시하도록했다. 노드의 개수가 100,000개이니까 100,000 * 100,000 배열을 만드는 것보다 효율적이다.