이번에 풀어본 문제는
프로그래머스 부대복귀 입니다.

📕 문제 링크

❗️코드

import java.util.*;

class Dest {
    int location, count;

    public Dest(int location, int count) {
        this.location = location;
        this.count = count;
    }
}

class Solution {
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        List<List<Integer>> map = new ArrayList<>();
        for (int i = 0; i <= n; i++) map.add(new ArrayList<>());

        for (int[] road: roads) {
            int fst = road[0];
            int sec = road[1];

            map.get(fst).add(sec);
            map.get(sec).add(fst);
        }

        int[] distance = new int[n + 1];
        Arrays.fill(distance, -1);
        distance[destination] = 0;
        Queue<Dest> q = new LinkedList<>();
        q.add(new Dest(destination, 0));

        while (!q.isEmpty()) {
            Dest cur = q.poll();

            for (int next: map.get(cur.location)) {
                if (distance[next] < 0) {
                    distance[next] = cur.count + 1;
                    q.add(new Dest(next, cur.count + 1));
                }
            }
        }

        int sourceLength = sources.length;
        int[] answer = new int[sourceLength];

        for (int i = 0; i < sourceLength; i++) answer[i] = distance[sources[i]];
        return answer;
    }
}

📝 풀이

간단하게 요약하자면 n개의 지역이 있을 때, destination과의 거리를 구하는 문제입니다.
각 지역은 roads에 주어진 관계로 연결되어있으며, 가중치는 1 고정입니다.
처음에는 다익스트라를 떠올렸지만, 생각해보니 가중치가 고정이기 때문에 도달 여부만 확인하고 도달하는데 까지의 횟수만 카운트해서 담아주면 충분할 것이라는 생각이 들어서 나름대로 구성해보았습니다.
결과적으로 제가 풀이한 방법은 bfs 탐색이며, 목적지인 destination 지역에서 시작하여 각 정점까지 도달하는데 까지 필요한 카운트를 배열에 담아주고, sources에 담긴 지역만 answer 배열에 담아 반환하여 해결해보았습니다.