부대 복귀 [자바]

 

🧫 문제 분석

✔️ 출처

부대 복귀 level 3

📖 문제

 

최단경로인데 길이가 1이라해서 그냥 BFS로 풀었다. 

 

몰랐던 사실인데 n이 10만이고, roads에서 모든 노드를 주지 않으므로, 메모리 낭비라고 생각해서 

HashMap을 사용하는것이 좋아보인다고 생각해서 사용했다. 

 

목적지 (destination)부터 끝노드까지 (탐색이 종료될때까지 ) 돌게 하되

방문한 곳이 source[i] 면 거리값을 저장한다. 

 

 물론 다익스트라 알고리즘을 쓰는게 맞는것 같다. 

내 로직보다 속도는 약 5배 정도 더 빠르다. 문제에서 최단 경로 라고 주어졌는데 

비용이 1이라는 말에 BFS로 밀고 가려해서 저렇게 짠 것이다. 

 

 

참고 

HashMap은 해시 충돌을 대비한 내부 구조 (엔트리 배열, 체이닝 등)로 인해 메모리 오버헤드가 있어

연결된 노드가 많고 전체 노드가 대부분 사용된다면 오히려 메모리를 차지할 수 있다고 한다. 

 

HashMap : 배열 + LinkedList(체이닝) or 레드 블랙 트리

충돌이 많을 때  최악의 경우 O(log N)

 

간선이 적은 경우 (희소 그래프) 일때는 Map

간선이 많은 경우 (조밀한 그래프) ArrayList[] 가 더 낫다. 

---

🔅 문제 풀이

import java.util.*;

class Solution {
    // n이 10만으로 2중배열은 안됨
    Map<Integer,ArrayList<Integer>> graphMap = new HashMap<>();
    Map<Integer, Integer> checkMap = new HashMap<>();

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

        // map에 노드 추가
        for (int i = 0; i < roads.length; i++) {
            if (!graphMap.containsKey(roads[i][0])) {
                graphMap.put(roads[i][0], new ArrayList<>());
            }

            if (!graphMap.containsKey(roads[i][1])) {
                graphMap.put(roads[i][1], new ArrayList<>());
            }
            graphMap.get(roads[i][0]).add(roads[i][1]);
            graphMap.get(roads[i][1]).add(roads[i][0]);
        }

        for (int i = 0; i < sources.length; i++) {
            checkMap.put(sources[i], i);
        }



        return bfs(sources, destination);
    }

    // 역으로 destination에서 끝노드까지 탐색하면서 source 가 있다면 그때그때 추가하는 방식
    private int[] bfs(int[] sources, int destination) {
        int[] answer = new int[sources.length];
        Arrays.fill(answer, -1);
        int idx = 0;

        // 방문 체크
        Set<Integer> set = new HashSet<>();


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

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

            // 목적지에 다다르면 비용 저장
            if (checkMap.containsKey(src[0])) {
                answer[checkMap.get(src[0])] = src[1];
            }

            // 시작 지점 노드 리스트 찾기
            ArrayList<Integer> list = graphMap.get(src[0]);
            if (list == null) continue;

            // BFS 탐색
            for (int region : list) {
                if (!set.contains(region)) {
                    q.add(new int[]{region, src[1] + 1});
                    set.add(region);
                }
            }
        }

        return answer;

    }
}

 

❗ 오답노트 / 필요한 지식

1. 최단 경로 = 다익스트라 라는 생각을 먼저 떠올려보자