프로그래머스 - Summer/Winter Coding(~2018) > 배달

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

배달

Dijkstra Algorithm

https://m.blog.naver.com/ndb796/221234424646
유튜브 강의와 블로그에 이해가 잘되게 작성되어서 자주 참조하니 링크를 남긴다

• 개념적인 부분
  현재 노드에서 갈 수 있는 노드까지의 가중치를 계산함
  근데 계산된 결과가 기존에 저장되어있던 가중치보다 작으면, 그 값을 갱신하고 방문해야할 노드로 저장

• 구현적인 부분
  가중치 테이블(int[] dist)을 N(혹은 N+1)만큼 생성하고, 최대값을 저장(Integer.MAX_VALUE)
  방문 여부 테이블(boolean[] visit)을 동일하게 N(혹은 N+1)만큼 생성하고, false값으로 초기화
  노드를 N(혹은 N+1)개 생성하고, 각 노드에 ArrayList<Node>를 할당해준다
  각각의 노드에 인접 노드 정보를 저장

  시작하는 노드(보통 0번 혹은 1번)를 우선순위 큐에 0의 가중치로 offer한 후 방문처리
  while(!queue.isEmpty()) 반복문 내에서 poll한 값이 방문하지 않으면 방문처리하고 진행
  꺼낸 curNode의 list 중에서 현재 가중치 + list에 기록된 가중치 < dist에 기록된 가중치 인 항목이 있다면, dist의 index에서 갱신해주고, 큐에 offer

  큐에 남아있는것이 없을때 까지 돌면, 모든 dist 배열이 완성됨

import java.util.ArrayList;
import java.util.PriorityQueue;

class Solution {
	static ArrayList<Node>[] node;
	static int[] dist;
	static boolean[] visit;
	
	class Node implements Comparable<Node> {
	    int index;
	    int weight;
	 
	    public Node(int index, int weight) {
	        this.index = index;
	        this.weight = weight;
	    }
	 
	    @Override
	    public int compareTo(Node o) {
	        return this.weight - o.weight;
	    }
	}
	
	
	public int solution(int N, int[][] road, int K) {
    	node = new ArrayList[N+1];
    	dist = new int[N+1];
    	visit = new boolean[N+1];
    	
    	for(int i = 1; i <= N; i++) {
    		node[i] = new ArrayList<Node>();
    		dist[i] = Integer.MAX_VALUE;
    		visit[i] = false;
    	}
    	
    	
    	for(int i = 0; i < road.length; i++) {
    		int s = road[i][0];
    		int e = road[i][1];
    		int w = road[i][2];
    		
    		//양방향으로 가중치 포함하여 생성
    		node[s].add(new Node(e, w));
    		node[e].add(new Node(s, w));
    	}
    	
    	PriorityQueue<Node> q = new PriorityQueue<Node>();
    	q.offer(new Node(1, 0));
    	dist[1] = 0;    	
    	while(!q.isEmpty()) {
    		Node cur = q.poll();
    		
    		if(visit[cur.index]) continue;
    		visit[cur.index] = true;
    		
    		//지금 꺼낸 node에 연결된 Node들을 확인
    		for(int i = 0; i < node[cur.index].size(); i++) {
    			Node linkNode = node[cur.index].get(i);
    			if(linkNode.weight + cur.weight < dist[linkNode.index]) {
    				dist[linkNode.index] = linkNode.weight + cur.weight;
    				q.offer(new Node(linkNode.index, linkNode.weight + cur.weight));
    			}
    			
    		}
    	}
    	
        int answer = 0;
        for(int i = 1; i < dist.length; i++) {
        	if(dist[i] <= K) answer++;
        }
        return answer;
    }
	
}