[백준] BOJ - 5972 택배 배송 자바 java (골드5)

https://www.acmicpc.net/problem/5972

5972번: 택배 배송

 

나의풀이

import java.util.*;
import java.io.*;
public class Main {
    static public class Node{
        int end, cost;
        public Node(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }
        public int getEnd(){
            return this.end;
        }
        
        public int getCost(){
            return this.cost;
        }
    }
    
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); //헛간개수 
        int m = Integer.parseInt(st.nextToken()); //길의 개수 
        List<Node>[] graph = new ArrayList[n+1];
        for(int i=0; i<=n ; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());//시작
            int b = Integer.parseInt(st.nextToken());//종료
            int c = Integer.parseInt(st.nextToken());//cost
            graph[a].add(new Node(b,c));
            graph[b].add(new Node(a,c));//양방향임에 주의

        }
        
        int [] dist = new int[50001]; //헛간의 최대 가능 개수 50000개 
        Arrays.fill(dist, Integer.MAX_VALUE); //헛간 초기화
        dist[0]=0;//0번째 배열은 안쓰는 배열임. 1부터 사용. 
        
        Queue<Node> q= new LinkedList<>();
        q.offer(new Node(0,1));//여물, 시작하는 헛간
        dist[1]=0; //시작 헛간 여물 0 
        
        while(!q.isEmpty()){
            Node temp=q.poll();
            int cost= temp.getEnd();//여물
            int start= temp.getCost();//지금위치
            
            if(dist[start] < cost){//이미 더 작은 수가 저장
                continue;
            }
            
            for(int i=0; i< graph[start].size();i++){
                int newCost= cost+graph[start].get(i).getCost();
                if(newCost < dist[graph[start].get(i).getEnd()]){//이미 저장된 거리보다 최단거리면 
                    dist[graph[start].get(i).getEnd()]=newCost;
                    q.offer(new Node(newCost, graph[start].get(i).getEnd()));
                }
            }
            
        }
        
        bw.write(Integer.toString(dist[n]));
        bw.flush();
        br.close();
        bw.close();
        
    }
}

Tip.

다익스트라 알고리즘 사용

양방향이므로 처음 graph 초기화 시 값 입력할 때 값을 양방향으로 넣어줘야 하는 것을 유의하자.

 

리스트로 2차원 배열을 선언할 경우, 인스턴스 생성시 for문 돌면서 각각의 배열 인덱스에 대해서도 new 키워드를 이용해 직접 초기화 해야 한다.