[프로그래머스] 배달 (JAVA)

프로그래머스

 

풀이

 

1. 다익스트라를 사용한 이유

시작 지점이 고정되어 있기 때문에 하나의 정점에서 모든 N개의 노드까지 최단 거리를 구해야 해 다익스트라를 사용했다.

 

플로이드 워셜은 다익스트라와 달리 모든 정점N 에서 모든 정점 N까지의 최단 거리를 구하는 알고리즘.

 

[알고리즘/ 그래프] 다익스트라(Dijkstra) vs 플로이드 와샬(Floyd Warshall) (JAVA)

 

그리고 다익스트라 알고리즘의 경우 간선에 가중치가 있을 경우엔 포멀한 BFS로만 해결할 수 없다고 하는데, 난 했는데(?)

우선순위 큐를 사용해서 해결하면 더 효율적인 것 같다.

또한, 다익스트라 알고리즘은 음의 가중치를 허용하지 않는다.

*음의 가중치를 가지고 있다면 벨만-포드 알고리즘을 사용해야 한다.

 

2. 새롭게 알게된 사실

class Node{
	int s;
    int a;
    int t;
    Node(int s, int a, int t){
    	this.s = s;
        this.a = a;
        this.t = t;
    }
}

ArrayList<ArrayList<Node>>town = new ArrayList<ArrayList<Node>>();
for(int i=0; i<N+1; i++){
    town.add(new ArrayList<Node>());
}

for(int i=0; i<cnt; i++){
    town.get(road[i][0]).add(new Node(road[i][0], road[i][1], road[i][2]));
    town.get(road[i][1]).add(new Node(road[i][1], road[i][0], road[i][2]));
}

 

배열 내에 ArrayList를 넣는 방식도 있지만, ArrayList안에 ArrayList를 넣어서 A에서 갈 수 있는 노드 목록을 넣어줄 수 있었다 (해당 방식으로 문제 해결)

 

Queue<Node> q = new LinkedList<>();
q.addAll(town.get(1));

 

가장 고민(?) 했던 지점은 town.get(idx)으로 가져온 idx가 갈 수 있는 모든 노드를 어떻게 큐에 담아줄 것인가.. 였는데

addAll(town.get(idx))를 사용하니 모든 노드를 한번에 담아줄 수 있었다.

 

3. 아이디어

BFS를 이용한 다익스트라 알고리즘 활용했다.

DFS는 해당 노드와 연결된 끝까지 확인하기 때문에 최단거리가 아님에도 계속해서 전진하기에 BFS를 사용해야 한다.

1에서 출발해 N번째 노드까지의 최단거리를 갱신해주면서 전체 N개의 노드를 갱신해준다! 방문했어도 재방문할 때 걸리는 시간이 짧다면 갱신해줘야 하기 때문에 방문처리가 아니라, 이미 저장되어있는 시간이 새로운 시간보다 클 경우, 더 작은 시간으로 갱신해줬다.

if(distance[v.a] > distance[v.s]+v.t){
	distance[v.a] = distance[v.s]+v.t;
 	q.addAll(town.get(v.a));
}

 

4. 시간복잡도

V: 노드의 숫자 / E: 간선의 숫자

기본 다익스트라 알고리즘의 시간 복잡도는 O(V^2)이다.

 

우선순위 큐를 사용한 2가지 방법으로 이를 좀 더 개선 할 수 있다.

•  각 정점마다 인접한 간선들을 모두 검사하는 작업이고
• 우선순위 큐에 원소를 넣고 삭제하는 작업이다.

모든 간선이 한번씩 검사된다는 점에서 첫 번째 작업이 O(E), 각 간선마다 우선수위 큐에 자료가 삽입 연산이 일어난다는 점에서 O(ElogE)이며, 이 둘을 합쳤을 때, (E+ElogE)의 시간복잡도는 O(ElogE)가 된다.

 

대개의 그래프의 경우 V^2 > E이므로 O(logE) = (logV)이고, 따라서, 시간 복잡도는 O(ElogV)가 될 수 있다.

 

 

전체코드

import java.io.*;
import java.util.*;

class Solution {
    static class Village{
        int s;
        int a;
        int t;
        Village(int s, int a, int t){
            this.s = s;
            this.a = a;
            this.t = t;
        }
    }
    static ArrayList<ArrayList<Village>> town;
    static long distance[];
    public int solution(int N, int[][] road, int K) {
        int cnt = road.length;
        town = new ArrayList<ArrayList<Village>>();
        for(int i=0; i<N+1; i++){
            town.add(new ArrayList<Village>());
        }
        for(int i=0; i<cnt; i++){
            town.get(road[i][0]).add(new Village(road[i][0], road[i][1], road[i][2]));
            town.get(road[i][1]).add(new Village(road[i][1], road[i][0], road[i][2]));
        }
        
        distance = new long[N+1];
        Arrays.fill(distance, 999999);
        distance[1] = 0;
        Delivery();
        
        int answer = 0;
        for(int i=0; i<N+1; i++){
            if(distance[i] <= K){
                answer++;
            }
        }

        return answer;
    }
    static void Delivery(){
        Queue<Village> q = new LinkedList<>();
        q.addAll(town.get(1));
        
        while(!q.isEmpty()){
            Village v = q.poll();
            
            if(distance[v.a] > distance[v.s]+v.t){
                distance[v.a] = distance[v.s]+v.t;
                q.addAll(town.get(v.a));
            }
        }
    }
}