백준_1916 최소비용 구하기(자바) / 다익스트라

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Back_1916 {
	static int N, M,start,end;
	static ArrayList<point>[] arr;
	static int dist[];
	static boolean visited[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		arr = new ArrayList[N+1];
		dist = new int[N+1];
		visited = new boolean[N+1];
		
		Arrays.fill(dist, Integer.MAX_VALUE);
		
		for (int i = 0; i < N+1; i++) {
			arr[i] = new ArrayList<>(); 
		}
		
		StringTokenizer st;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int fee = Integer.parseInt(st.nextToken());
			arr[from].add(new point(to, fee));
		}
		st = new StringTokenizer(br.readLine());
		start = Integer.parseInt(st.nextToken());
		end = Integer.parseInt(st.nextToken());
		
		dijkstra();
		System.out.println(dist[end]);
	}
	private static void dijkstra() {
		PriorityQueue<point> pq = new PriorityQueue<>();
		pq.add(new point(start, 0));
		dist[start] = 0;
		
		while(!pq.isEmpty()) {
			point p = pq.poll();
			
			if(!visited[p.x]) {
				visited[p.x] = true;
				
				for(point tmp : arr[p.x]) {
					if(dist[p.x]+tmp.w<dist[tmp.x]) {
						dist[tmp.x] = dist[p.x] + tmp.w;
						pq.offer(new point(tmp.x, dist[tmp.x]));
					}
				}
			}

		}
	}
	static class point implements Comparable<point>{
		int x;
		int w;
		public point(int x, int w) {
			super();
			this.x = x;
			this.w = w;
		}
		@Override
		public int compareTo(point o) {
			return this.w - o.w;
		}
		
	}
	
}

 

※ 내 생각

이 문제는 다익스트라 및 그리디 알고리즘을 활용하는 문제입니다.

ArrayList를 배열로 만들어 각 도착지에 대한 w 비용을 담을 수 있습니다.
모든 값을 받으면 다익스트라 메소드를 만들어줍니다.

메소드에서는 PriorityQueue를 활용하여 w를 비교 하면서 값을 넣을 수 있습니다.
visited로 방문 여부 처리를 해주면 시간을 아낄 수 있습니다.