[프로그래머스] 132266. 부대 복귀 JAVA

프로그래머스

---

❓ 문제

강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 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	return
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]

 

---

✍🏻 풀이

• 각 인덱스별로 이동하는 위치의 정보를 담아줄 배열 리스트를 선언해주었다.
• 리턴할 값을 담을 배열을 ans로 선언해주었다.

 

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

class Solution {
   public int[] solution(int n, int[][] roads, int[] sources, int destination) {
      ArrayList<ArrayList<Integer>> roads_list = new ArrayList<>();
      int[] ans = new int[sources.length];
   }
}

---

• 반복문을 돌며, 배열 리스트를 초기화 해주었다.
• 다시 반복문을 돌며, 배열 리스트에 각 인덱스 별로 연결된 지역의 번호들을 입력해주었다.
• 각 위치별로 복귀할 수 있는 시간을 담을 배열을 선언해주고, 복귀할 수 없으면 -1을 리턴하기 때문에 -1로 채워주었다.
• 도착지점은 0이기 때문에 0 값을 할당해주었다.

 

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

class Solution {
   public int[] solution(int n, int[][] roads, int[] sources, int destination) {
      
      ...

      for (int i = 0; i < n + 1; i++) roads_list.add(new ArrayList<>());
      for (int[] r : roads) {
         roads_list.get(r[0]).add(r[1]);
         roads_list.get(r[1]).add(r[0]);
      }

      int[] dist = new int[n + 1];
      Arrays.fill(dist, -1); // 갈 수 없으면 -1
      dist[destination] = 0; // 도착 지점은 0
   }
}

---

• 큐를 이용해 도착 지점부터 각 지점까지 걸리는 시간을 구해주었다. 
• 도착 지점에서 해당 위치까지 걸리는 시간과 해당 위치에서 도착 지점까지 걸리는 시간은 같기 때문이다.
• 반복문을 돌며, sources에 담긴 위치에서 도착지점까지 걸리는 시간을 ans에 담아주었다.

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

class Solution {
   public int[] solution(int n, int[][] roads, int[] sources, int destination) {
      
      ...

      Queue<int[]> q = new LinkedList<>();
      q.add(new int[]{destination, 0});

      while (!q.isEmpty()) {
         int[] cur = q.poll();

         for (int next : roads_list.get(cur[0])) {
            if (dist[next] < 0) {
               dist[next] = cur[1] + 1;
               q.add(new int[]{next, cur[1] + 1});
            }
         }
      }

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

      return ans;
   }
}

---

✍🏻 최종

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

class Solution {
   public int[] solution(int n, int[][] roads, int[] sources, int destination) {
      ArrayList<ArrayList<Integer>> roads_list = new ArrayList<>();
      int[] ans = new int[sources.length];

      for (int i = 0; i < n + 1; i++) roads_list.add(new ArrayList<>());
      for (int[] r : roads) {
         roads_list.get(r[0]).add(r[1]);
         roads_list.get(r[1]).add(r[0]);
      }

      int[] dist = new int[n + 1];
      Arrays.fill(dist, -1); // 갈 수 없으면 -1
      dist[destination] = 0; // 도착 지점은 0

      Queue<int[]> q = new LinkedList<>();
      q.add(new int[]{destination, 0});

      while (!q.isEmpty()) {
         int[] cur = q.poll();

         for (int next : roads_list.get(cur[0])) {
            if (dist[next] < 0) {
               dist[next] = cur[1] + 1;
               q.add(new int[]{next, cur[1] + 1});
            }
         }
      }

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

      return ans;
   }
}

---