항해99 23일차 TIL ( 배달 / 프로그래머스 )

문제                        

프로그래머스

 

 

1 번째 시도                         

• 가중치가 있는 그래프
  • 해결법: 다익스트라 알고리즘
• 관계도에따라 map을 만든다.
• start에서 갈 수 있는 곳들을 탐색하고 disct배열에 기록해둔다.
• disct 에서 방문한 노드를 제외한 노드중에 가장 가까운곳으로 간다.
• 위의 사항들을 반복한다.

import java.util.*;

class Solution {
    
    boolean[] visited;
    int[] disct;
    int[][] map;
    int n;
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        visited = new boolean[N+1];
        disct = new int[N+1];
        map = new int[N+1][N+1];
        n = N;
        Arrays.fill(disct, Integer.MAX_VALUE);
        //자기자신은 거리가 0
        for (int i = 0; i <= N; i++) disct[i] = Integer.MAX_VALUE; 

        disct[1] = 0;

        //인접행렬 첫 번째 초기화
         for (int i = 0; i <= N; i++) {
             Arrays.fill(map[i], Integer.MAX_VALUE);
        }
        
        //인접행렬 두 번째 초기화 
        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;
            }
        }
        
        dijkstra();

        for(int i = 1; i <= n; i++) {
            if(K >= disct[i])
                answer++;
        }
        return answer;
    }
    
    public void dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        
        pq.add(new Node(1,0));
        while(!pq.isEmpty()) {
            Node node = pq.poll();
            int edge = node.edge;
            int weight = node.weight;
            visited[edge] = true;

            for(int i = 1; i <= n; i++) {
                //직접 갈 수 있고
                if(map[edge][i] != Integer.MAX_VALUE) {
                   // 선택되지 않은 노드이고 기존 disct보다 값이 작은
                    if (!visited[i] && disct[i] > weight + map[edge][i]) {
                        disct[i] = weight + map[edge][i]; 
                        pq.add(new Node(i, weight + map[edge][i]));
                    }
                }
            }
        }
    }
     class Node implements Comparable<Node>{
        int edge;
        int weight;
        
        public Node(int edge, int weight) {
            this.edge = edge;
            this.weight = weight;
        }
        
        public int compareTo(Node node) {
            return this.weight - node.weight;
        }
    }
}

 

 

배운점

• 다익스트라 알고리즘 with 우선순위 큐
• 우선순위 큐 메소드
  • add()
  • poll()
  • peek()
  • (추후 정리 후 포스팅 예정)
• 우선순위 큐 배열이 아닌 Node 클래스로 넣기