백준 1916 : 최소비용 구하기 [Java]

문제

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

1916번: 최소비용 구하기

코드

package baekjoon;

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

public class Main_1916 {

	static List<Bus>[] graph;
	static int[] cost;
	static int N, M;
	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()); //버스의 개수
		StringTokenizer st;
		graph = new ArrayList[N + 1];
		for(int i = 1; i <= N; i++) {
			graph[i] = new ArrayList<>();
		}
		cost = new int[N + 1];
		Arrays.fill(cost, Integer.MAX_VALUE);
		visited = new boolean[N + 1];
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int busStart = Integer.parseInt(st.nextToken());
			int busEnd = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			graph[busStart].add(new Bus(busEnd, cost));
		}
		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		cost[start] = 0;
		find(start);
		System.out.println(cost[end]);
	}
	
	static void find(int start) {
		PriorityQueue<Bus> pq = new PriorityQueue<>();
		pq.add(new Bus(start, 0));
		while(!pq.isEmpty()) {
			Bus now = pq.poll();
			if(!visited[now.city]) {
				visited[now.city] = true;
				for(Bus next : graph[now.city]) {
					if(cost[next.city] > cost[now.city] + next.cost) {
						cost[next.city] = cost[now.city] + next.cost;
						pq.add(new Bus(next.city, cost[next.city]));
					}
				}
			}
		}
	}
	
	static class Bus implements Comparable<Bus>{
		int city;
		int cost;
		public Bus(int city, int cost) {
			super();
			this.city = city;
			this.cost = cost;
		}
		@Override
		public int compareTo(Bus o) {
			// TODO Auto-generated method stub
			return this.cost - o.cost;
		}
		
	}

}

 

접근 방법

문제를 읽어보면 결국 도시의 개수 = 정점의 개수, 버스의 개수 = 간선의 개수, 정점간의 최소 비용 구하기 즉, dijkstra임을 알 수 있다.

처음에는 2퍼센트 정도에서 틀렸다고 나왔는데 게시판에서 반례를 보니

같은 정점들에 대해서 여러개의 간선이 있음을 간과했다.

예를들어 1번 정점에서 2번 정점으로 가중치가 1인 간선과 10인 간선 두가지가 동시에 존재할 수 있어서 그 부분을 고쳐주었다.

그랬더니 시간 초과가 발생했다ㅋㅋ

알고보니 내가 visited선언만 해놓고 사용을 안하고 있었다... 잊지말고 방문 체크해주기!