[ 알고리즘 ] 코딩 - Programmers - 배달.java

---

문제 링크

programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

---

문제 개요

프로그래머스 - Level 2 - (자바) 배달 - 다익스트라 (시작점부터 최단경로 찾기)     1번 시작점부터 다른 모든 정점까지의 최단경로가 K이하인 정점의 갯수를 구하는 문제!

---

 

로직

Step 01. 정점 번호, 누적 거리를 저장할 Class를 하나 만든다.             이때 Comparator를 이용해서 누적거리의 최단 거리를 기준으로 정렬 할 수 있게 한다  Step 02. 입력 값 중에 정점으로 가는 여러가지 길이 있으니, 그 중 최소인 값을 저장한다              (이 방법이 싫다면 모든 정점간 거리를 저장하고 PriorityQueue에 거리순으로 저장후 최단 거리만을 뽑아서              할 수 있을 듯 하다.) Step 03. 입력받은 정점과 가중치를 기준으로 1번 정점부터 시작하여 다익스트라를 적용. distance 배열을 생성한다. Step 04. distance배열의 값중에 K 이하인 거리의 갯수를 세어 return 하면 정답!

---

코드

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
	static class Vertex implements Comparable<Vertex> {
      int no, totalDistance; // 출발지에서 오는 최단거리.

      public Vertex(int no, int totalDistance) {
        this.no = no;
        this.totalDistance = totalDistance;
      }

      @Override
      public int compareTo(Vertex o) {
      	return this.totalDistance - o.totalDistance; // 최단거리가 작은 거 부터 정렬
      }
  }

    public int solution(int N, int[][] road, int K) {
      int answer = dijkstra(road, N, K);
      return answer;
    }

		/** */
     private int dijkstra(int[][] road, int N, int K) {
     	int[][] matrix = new int[N + 1][N + 1];
          for (int i = 0; i < road.length; i++) { // 정점에 연결된 가중치의 최소를 저장
            if (matrix[road[i][0]][road[i][1]] == 0) {
              matrix[road[i][0]][road[i][1]] = road[i][2];
              matrix[road[i][1]][road[i][0]] = road[i][2];
            } else {
              if (matrix[road[i][0]][road[i][1]] > road[i][2]) {
                matrix[road[i][0]][road[i][1]] = road[i][2];
                matrix[road[i][1]][road[i][0]] = road[i][2];
              }
            }
      	  }

          int start = 1;
          int end = N;
          final int INFINITY = Integer.MAX_VALUE;

          int[] distance = new int[N + 1];
          boolean[] visited = new boolean[N + 1];

          PriorityQueue<Vertex> pQueue = new PriorityQueue<Vertex>();

          Arrays.fill(distance, INFINITY);
          distance[start] = 0;
          pQueue.offer(new Vertex(start, distance[start]));

          Vertex current = null;

          while (!pQueue.isEmpty()) {
            // 1단계 : 방문하지 않은 정점들 중 출발지에서 자신까지 오는 비용이 가장 짧은 정점을 고려할 경우지 선택.
            current = pQueue.poll();

            visited[current.no] = true;
            // if(current.no == end) break;

            // 2단계 : 선택된 current 정점을 경유지로 해서 아직 방문하지 않은 다른 정점으로의 최단거리 비용을 계산.
            // 유리하면 update
            for (int j = 1; j <= N; j++) {
              if (!visited[j] && matrix[current.no][j] != 0
              && distance[j] > current.totalDistance + matrix[current.no][j]) {
                  distance[j] = current.totalDistance + matrix[current.no][j];
                  pQueue.offer(new Vertex(j, distance[j]));
              }
            }
          } // 다익스트라 end

		int res = 0;

        // K이하의 거리 갯수
        for (int i = 1; i <= N; i++) {
          if (distance[i] <= K)
           res++;
          }
        return res;
	}
 }