부대복귀

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

문제설명

• 주어진 파라미터: int n, int[][] roads, int[] sources, int destination
  • n: 총 지역 수
  • 길 정보: roads
  • 부대원 위치: sources
  • 부대 지역: destination
• 반환값: int[]
  • sources 원소 순서대로 복귀할 수 있는 최단 시간 담은 배열
• 지도 정보를 이용해 최단 시간에 복귀하고자 함
• 임무 시작과 다르게 되돌아오는 경로가 없어져 복귀가 불가능할 수 있음

풀이방식

1. (풀이방식1)

   1. 인접 리스트를 활용한 BFS로 풀이

      → 양쪽으로 이동이 가능해야하기때문에 map을 구성하되 양쪽 노드 모두 추가해주기

   2. sources를 돌며 source가 root가 됨

      → source 별로 queue while문 별도 진행

      → 꺼낸 값이 destination과 같을 경우 cnt return

      → 없을 경우 -1

   3. answer 배열 return

      ⇒ 시간초과

2. (풀이방식2)

   1. BFS를 사용하지만 나오는 모든 숫자를 answerList에 추가
   2. source를 돌며 answerList index로 answer 채우기
   3. ⇒ 한번의 수행으로 모든 경우를 찾을 수 있음
   
   

코드

import java.util.*;

class Solution {
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        Map<Integer, Boolean> visited = new HashMap<>();
        // boolean[] visited = new boolean[n];
        int[] answer = new int[sources.length];
        int answerIdx = 0;

        // 인접리스트 graph (key: 도착지, value: 출발지)
        for(int[] road : roads){
            int start = road[0];
            int end = road[1];

            // 출발지 기준 추가
            if(!graph.containsKey(start)){
                graph.put(start, new ArrayList<>(Arrays.asList(end)));
            }else{
                graph.get(start).add(end);
            }

            // 도착지 기준 추가
            if(!graph.containsKey(end)){
                graph.put(end, new ArrayList<>(Arrays.asList(start)));
            }else{
                graph.get(end).add(start);
            }
        }

        for(int source : sources){
            // 도착지일 경우 0
            if(source == destination){
                answer[answerIdx++] = 0;
                continue;
            }

            // 초기 세팅
            Queue<int[]> q = new ArrayDeque<>();
            visited.clear();
            visited.put(source, true);
            q.add(new int[]{source, 1});

            while (!q.isEmpty()) {
                int[] cur = q.poll();
                int curV = cur[0];
                int curDist = cur[1];
                
                if(!graph.containsKey(curV)){ // containsKey가 안될 경우 X 
                    answer[answerIdx++] = -1;
                }else{
                    for(int nextV : graph.get(curV)){
                        if(nextV == destination){
                            answer[answerIdx++] = curDist;
                            q.clear();
                            break;
                        }else{
                            if(!visited.containsKey(nextV)){
                                visited.put(nextV, true);
                                q.add(new int[]{nextV, curDist+1});
                            }
                        }
                    }

                }
            }

        }

        return answer;
    }
}

• visited 관리 자료구조 변경: Map → int[]
• queue내에 노드와 거리를 함께 저장: queue<노드 , 거리>

import java.util.*;

class Solution {
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        boolean[] visited = new boolean[n+1]; 
        int[] answerList = new int[n + 1];
        
        Arrays.fill(visited, false);
        Arrays.fill(answerList, -1);
        
        // 인접리스트 graph (key: 도착지, value: 출발지)
        for(int[] road : roads){
            int start = road[0];
            int end = road[1];

            // 출발지 기준 추가
            if(!graph.containsKey(start)){
                graph.put(start, new ArrayList<>(Arrays.asList(end)));
            }else{
                graph.get(start).add(end);
            }

            // 도착지 기준 추가
            if(!graph.containsKey(end)){
                graph.put(end, new ArrayList<>(Arrays.asList(start)));
            }else{
                graph.get(end).add(start);
            }
        }

        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{destination, 0});
        visited[destination] = true;
        answerList[destination] = 0;
        
        while(!q.isEmpty()){
            int[] cur = q.poll();
            int curV = cur[0];
            int curDist = cur[1];
            
            for(int nextV : graph.get(curV)){
                if(!visited[nextV]){
                    q.add(new int[]{nextV, curDist+1});
                    visited[nextV] = true;
                    answerList[nextV] = curDist+1;
                }
            }
        }
        
        int[] answer = new int[sources.length];
        int answerIdx = 0;
        for(int source: sources){
            answer[answerIdx++] = answerList[source];
        }

        return answer;
    }
}

---

BFS에 대해서 더 자세하게 공부해야할거같네요 ㅜ..