부대복귀-BFS

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

프로그래머스

[문제요약]

• 2 X N 크기의 부대 지도
• 부대원들은 각각 흩어져서 sources 배열 위치에 위치하고 있음
• 각각 위치하고 있는 부대원들이 destination 위치에 부대에 복귀할 수 있는 최단 거리를 구하는 것이 목표

 

[문제풀이]

이전 보물섬 문제를 푼 알고리즘과 유사하지만 일부분이 다릅니다.

https://suho0303.tistory.com/27

2589-보물섬

이 문제는 영역마다 bfs를 돌려주는 것이 아닌 도착 부대 지점에서만 bfs를 '한번'만 돌려줘도 된다는 것입니다.

 

각각 지점마다 방문처리를 할때 방문 배열에 동일하게 거리를 저장하면서 진행하게 되면,

 

출력시에 sources의 위치의 방문 배열 안 최단 거리만 출력하면 되는 것이죠.

 

[코드]

import java.util.*;

public class 부대복귀 {

    public static int[] bfs(int destination, ArrayList<ArrayList<Integer>> rlt, int[]visit) {

        Queue<Integer> queue = new LinkedList<>();
        queue.add(destination);
        visit[destination] = 0;

        while (!queue.isEmpty()) {
            int cur = queue.poll();

            for (Integer integers : rlt.get(cur)) {
                if (visit[integers] == -1) {
                    queue.add(integers);
                    visit[integers] = visit[cur] + 1;
                }
            }
        }

        return visit;
    }

    public static void main(String[] args) {

        int n = 3;
        int destination = 1;
        int[][] roads = {{1, 2}, {2, 3}};
        int[] sources = {2, 3};
        int[] visit = new int[n+1];

        ArrayList<ArrayList<Integer>>rlt = new ArrayList<>();
        for (int i = 0; i < n+1; i++) {
            rlt.add(new ArrayList<>());
            visit[i] = -1;
        }

        for (int[] i : roads) {
            rlt.get(i[0]).add(i[1]);
            rlt.get(i[1]).add(i[0]);
        }

        ArrayList<Integer> visit_rlt = new ArrayList<>();
        bfs(destination, rlt, visit);
        for (int source : sources) {
            visit_rlt.add(visit[source]);
        }
        System.out.println(visit_rlt);
        System.out.println(Arrays.toString(visit));
    }
}