[프로그래머스/JAVA 자바] 배달

 

프로그래머스

문제풀이

1. 다익스트라 ( Dijkstra ) 문제.

 

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

2. 위 예제로 다익스트라를 적용한 예시.

특정 노드에서 다른 노드로 가는데 걸리는 시간

여기서 우리는 1번 노드를 기준으로 잡고 최단 경로를 구하는게 목적이다. 아래부터는 1번 노드를 기준으로 최단 경로를 구하는 방법을 차례로 보여준다.

1번 노드에서 다른 노드로 가는데 걸리는 시간

위 노드를 보면 , 1 노드를 제외하고 가장 적은 시간이 걸리는 노드는 2번 노드이다. 그렇다면 다음은 2번에서 다른 노드로 가는데 걸리는 시간을 갱신해준다. ( 시간이 줄어들면 갱신, 늘어나면 갱신 X ,

계산 할때는 1노드에서 N노드로의 시간 VS 1노드에서 N 노드로 가는 시간 + N노드에서 K노드로 가는 시간을 고려 )

1노드 -> 2노드 -> 다른 노드

다음으로 , 1 과 2 노드는 계산이 완료 됐으므로 , 3  4  5 노드 중 가장 적은 시간이 걸리는 노드를 계산. ( 4 노드가 가장 적게 걸림 )

최종 시간 계산

위 표를 결과로 K 시간 ( 3시간 ) 안에 갈 수 있는 노드는 1 , 2 , 4 , 5 노드로 총 4개이다.

 

나의풀이 ( 코드 )

class Solution {
    static final int INF = 500001;
    static boolean[] visited;
    static int[] dist;
    static int[][] map;
    static int cnt = 0;
    
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        map = new int[N + 1][N + 1];
        visited = new boolean[N + 1];
        dist = new int[N + 1];
        visited[1] = true;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if(i==j) continue;
                map[i][j] = INF;
            }
        }

        for (int i = 0; i < road.length; i++) {
            int a = road[i][0];
            int b = road[i][1];
            int c = road[i][2];

            if (map[a][b] > c) {
                map[a][b] = c;
                map[b][a] = c;
            }
        }

        for (int i = 2; i <= N; i++) {
            dist[i] = INF;
        }

        dijkstra(N, K);

        answer = cnt;
        return answer;
    }
    
    static void dijkstra(int N, int K) {

        for (int i = 1; i < N; i++) {
            int min = INF;
            int idx = 1;

            for (int j = 2; j <= N; j++) {
                if (!visited[j] && min > dist[j]) {
                    idx = j;
                    min = dist[j];
                }
            }

            visited[idx] = true;

            for (int j = 2; j <= N; j++) {
                if (dist[j] > dist[idx] + map[idx][j]) {
                    dist[j] = dist[idx] + map[idx][j];
                }
            }

        }

        for (int i = 1; i <= N; i++) {
            if (dist[i] <= K) {
                cnt++;
            }
        }

    }
}