프로그래머스) 부대복귀

⏰문제

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

프로그래머스

 

문제 설명

강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다.

강철부대가 위치한 지역을 포함한 총지역의 수 `n`, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 `roads`, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 `sources`, 강철부대의 지역 `destination`이 주어졌을 때, 주어진 `sources`의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간을 담은 배열을 return하는 solution 함수를 완성해주세요. 복귀가 불가능한 경우 해당 부대원의 최단시간은 -1입니다. 

 

 

제한사항

• 3 ≤ `n` ≤ 100,000
  • 각 지역은 정수 1부터 `n`까지의 번호로 구분됩니다.
• 2 ≤`roads`의 길이 ≤ 500,000
  • `roads`의 원소의 길이 = 2
  • `roads`의 원소는 [a, b] 형태로 두 지역 a, b가 서로 왕복할 수 있음을 의미합니다.(1 ≤ a, b ≤ n, a ≠ b)
  • 동일한 정보가 중복해서 주어지지 않습니다.
    • 동일한 [a, b]가 중복해서 주어지지 않습니다.
    • [a, b]가 있다면 [b, a]는 주어지지 않습니다.
• 1 ≤ `sources`의 길이 ≤ 500
  • 1 ≤ `sources[i]` ≤ n
• 1 ≤ `destination`≤ n

---

입출력

n	roads	sources	destination	result
3	[[1, 2], [2, 3]]	[2, 3]	1	[1, 2]
5	[[1, 2], [1, 4], [2, 4], [2, 5], [4, 5]]	[1, 3, 5]	5	[2, -1, 0]

 

---

입출력 예 설명

입출력 예 #1

• 지역 2는 지역 1과 길로 연결되어 있기 때문에, 지역 2에서 지역 1의 최단거리는 1입니다.
• 지역 3에서 지역 1로 이동할 수 있는 최단경로는 지역 3 → 지역 2 → 지역 1 순으로 이동하는 것이기 때문에, 지역 3에서 지역 1의 최단거리는 2입니다.
• 따라서 [1, 2]를 return합니다.

입출력 예 #2

• 지역 1에서 지역 5의 최단경로는 지역 1 → 지역 2 → 지역 5 또는 지역 1 → 지역 4 → 지역 5 순으로 이동하는 것이기 때문에, 최단거리는 2입니다.
• 지역 3에서 지역 5로 가는 경로가 없기 때문에, 지역 3에서 지역 5로 가는 최단거리는 -1입니다.
• 지역 5에서 지역 5는 이동할 필요가 없기 때문에, 최단거리는 0입니다.
• 따라서 [2, -1, 0]을 return합니다.

 

💡풀이

최단경로를 구하라고 해서 BFS를 이용해서 풀었다. 익숙하게 인접행렬을 이용해서 풀었는데 메모리 초과가 나와버렸다. 풀이 문제는 아닌 것 같아서 찾아보니 인접리스트를 이용해서 풀길래 다시 코드를 짜 보았다. 

인접행렬 코드

 

⌨️ 코드

import java.util.*;

class Solution {
        /**
         * @param n : 강철부대가 위치한 지역을 포함한 총 지역의 수
         * @param roads : 두 지역을 왕복할 수 있는 길 정보
         * @param sources : 각 부대원이 위치한 서로 다른 지역들
         * @param destination : 강철부대의 지역
         * @return : 강철부대로 복귀할 수 있는 최단시간 , 복귀 불가한 경우 -1
         */
        List<Integer>[] list;
        int[] visited;
        static int N;
        public int[] solution(int n, int[][] roads, int[] sources, int destination) {
            int[] answer = new int[sources.length];
            N = n+1;
            list = new LinkedList[N];

            for (int i = 0; i <= n; i++) {
                list[i] = new LinkedList<>();
            }
            for(int i= 0; i < roads.length; i++){
                int a = roads[i][0];
                int b = roads[i][1];
                list[a].add(b);
                list[b].add(a);
            }

            for (int i = 1; i <= n; i++) {
                Collections.sort(list[i]); // 방문 순서를 위해 오름차순 정렬
            }

            int idx = 0;
            visited = new int[N];

            BFS(destination);

            for(int i=0; i < sources.length; i++){
                int start = sources[i];
                if(visited[start] == 0){
                    answer[idx++] = -1;
                }
                else{
                    answer[idx++] = visited[start]-1; //-1은 출발지 빼주기 
                }
            }
            return answer;
        }

        private void BFS(int destination) {
            Queue<Integer> q = new LinkedList<>();


            q.add(destination);
            visited[destination]++;

            while(!q.isEmpty()){
                int now = q.poll();
                for(int next : list[now]){
                    if(visited[next] == 0){ //들리지 않았다면
                        q.add(next);
                        visited[next] = visited[now]+1;
                    }
                }
            }
        }
    }

 

 

2차원 배열이용해서 풀은 풀이 => 메모리 초과 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
        /**
         * @param n : 강철부대가 위치한 지역을 포함한 총 지역의 수
         * @param roads : 두 지역을 왕복할 수 있는 길 정보
         * @param sources : 각 부대원이 위치한 서로 다른 지역들
         * @param destination : 강철부대의 지역
         * @return : 강철부대로 복귀할 수 있는 최단시간 , 복귀 불가한 경우 -1
         */
        static int[][] map;
        int[] visited;

        static int N;
        public int[] solution(int n, int[][] roads, int[] sources, int destination) {
            int[] answer = new int[sources.length];

            map = new int[n+1][n+1];
            N = n+1;

            for(int i= 0; i < roads.length; i++){
                int a = roads[i][0];
                int b = roads[i][1];
                map[a][b] = 1;
                map[b][a] = 1;
            }

            int idx = 0;
            visited = new int[N];
            BFS(destination);

            for(int i=0; i < sources.length; i++){
                int start = sources[i];
                if(visited[start] == 0){
                    answer[idx++] = -1;
                }
                else{
                    answer[idx++] = visited[start]-1; //-1은 출발지 빼주기
                }
            }


            return answer;
        }

        private void BFS(int destination) {
            Queue<Integer> q = new LinkedList<>();
            q.add(destination);
            visited[destination]++;

            while(!q.isEmpty()){
                int now = q.poll();

                for(int i=1; i<map.length; i++){
                    if(map[now][i] == 1 && visited[i] == 0){ //map에 길이 있고, 들리지 않았다면
                        q.add(i);
                        visited[i] = visited[now]+1;
                    }
                }
            }
        }
    }

 

 

📣 comment

배열이 편해서 BFS를 보통 배열로 풀었는데, 인접 리스트에 익숙해져야겠다.