[프로그래머스/Level3] 부대 복귀 (JAVA)

📖 문제

 

프로그래머스

 

 

 

💡  풀이 방식

• BFS

필요 자료구조
- 인접 리스트
- 1차원 최단 거리 배열 (destination으로부터의 최단 거리를 나타냄)

 

1. 인접 리스트 그래프 graph에 길 정보를 저장한다.

2. 최단 거리 배열을 모두 최댓값으로 저장한다.

3. 시작점 destination부터 BFS를 진행하며 최단 거리 배열을 채운다.

for(int next : graph[now]) {                
    if(dist[now] + 1 < dist[next]) {    // 최단 거리 갱신
        dist[next] = dist[now] + 1;
        q.add(next);
    }
}

 

 

 

🔺 코드

1. List<List<Integer>>를 활용한 풀이

import java.util.*;
 
class Solution {
    static final int INF = Integer.MAX_VALUE;
    static List<List<Integer>> graph;
    static int[] dist;    // 최단 거리 배열
    
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        graph = new ArrayList<>();
        for(int i = 0 ; i <= n ; i++) {
            graph.add(new ArrayList<>());
        }
                
        for(int[] r : roads) {            
            graph.get(r[0]).add(r[1]);
            graph.get(r[1]).add(r[0]);
        }
        
        dist = new int[n+1];
        Arrays.fill(dist, INF);
       dijkstra(n, destination);
        
        int[] answer = new int[sources.length];
        for(int i = 0 ; i < sources.length ; i++) {
            int v = dist[sources[i]];
            answer[i] = (v == INF) ? -1 : v;
        }
        
        return answer;
    }
    
    private static void dijkstra(int n, int destination) {
        Queue<Integer> q = new LinkedList<>();
        q.add(destination);
 
        dist[destination] = 0;    // 시작점        
        
        while(!q.isEmpty()) {
            int now = q.poll();
            
            for(int i = 0 ; i < graph.get(now).size() ; i++) {
                int next = graph.get(now).get(i);
                
                // 최단 거리 갱신
                if(dist[now] + 1 < dist[next]) {
                    dist[next] = dist[now] + 1;
                    q.add(next);
                }
            }
        }     
    }
}

 

 

 

 

2. List<Integer>[]>를 활용한 풀이 ✅

import java.util.*;
 
class Solution {
    static final int INF = Integer.MAX_VALUE;
    static List<Integer>[] graph;
    static int[] dist; // 최단 거리 배열
    
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        graph = new ArrayList[n+1];
        for(int i = 0 ; i <= n ; i++) {
            graph[i] = new ArrayList<>();
        }
                
        for(int[] r : roads) {            
            graph[r[0]].add(r[1]);
            graph[r[1]].add(r[0]);
        }
        
        dist = new int[n+1];
        Arrays.fill(dist, INF);
        
       dijkstra(n, destination);
        
        int[] answer = new int[sources.length];
        for(int i = 0 ; i < sources.length ; i++) {
            int v = dist[sources[i]];
            answer[i] = (v == INF) ? -1 : v;
        }
        
        return answer;
    }
    
    private static void dijkstra(int n, int destination) {
        Queue<Integer> q = new LinkedList<>();
        q.add(destination);
        
        dist[destination] = 0;    // 시작점   
        
        while(!q.isEmpty()) {
            int now = q.poll();
            
            for(int next : graph[now]) {                
                if(dist[now] + 1 < dist[next]) {    // 최단 거리 갱신
                    dist[next] = dist[now] + 1;
                    q.add(next);
                }
            }
        }     
    }
}

 

 

 

➕ 다른 풀이 방식

1) 다익스트라 (우선순위 큐 O)를 사용한 풀이 1

[프로그래머스] 부대복귀 (Java)

 

 

2) 다익스트라를 활용한 풀이 2

 

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

---

💦 어려웠던 점

-처음에 플로이드-와샬 풀었다가 O(N^3)의 시간 복잡도로 인해 시간 초과, 메모리 초과 이슈 발생.. (아무래도 10만을 세제곱하면 오바니까..)

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

[pro] 프로그래머스 level3 132266 부대복귀 (Java) - 다익스트라

 

✔ 문제 시간 복잡도 관련 참

프로그래머스 - 부대복귀(Java)