Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

25. 최단 경로

그래프의 간선에 가중치가 없으면 BFS로 최단거리를 찾을 수 있습니다. 가중치가 있다면 어떨까요?

Java / Python

6. KCM Travel

10217번

간선을 사용하는 비용과 예산 제약이 있을 때 다이나믹 프로그래밍으로 최단거리를 찾는 문제

이번 문제는 각 공항들간 티켓가격과 이동시간이 주어질 때, 인천에서 LA로 갈 수 있는 가장 빠른 길을 찾는 문제입니다.
가중치가 1이 아니므로 DFS, BFS가 아닌 다익스트라, 벨만 포드, 플로이드 와샬을 사용해야 하는 문제로,
한 노드 ▶ 노드 이므로 다익스트라, 벨만 포드,
그 중에서도 음의 가중치가 없기 때문에 다익스트라를 사용하는 문제입니다.

• Java

import java.io.*;
import java.util.*;

public class Main {
	static class Airport implements Comparable<Airport>{
		int end;
		int cost;
		int time;

		public Airport(int end, int cost, int time){
			this.end = end;
			this.cost = cost;
			this.time = time;
		}

		@Override
		public int compareTo(Airport airport) {
			if(this.time == airport.time) return cost - airport.cost;
			return this.time - airport.time;
		}
	}
        
	static final int INF = 1000000000;
	static int[][] dp; 
	static int N, M, K;
	static List<Airport>[] list;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
		StringTokenizer st = null;
        
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
        
		for(int t = 0; t < T; t++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
            
			dp = new int[N + 1][M + 1];
			list = new ArrayList[N + 1];

			for(int i = 0 ; i <= N; i++)
				Arrays.fill(dp[i], INF);

			for(int i = 0; i <= N; i++)
				list[i] = new ArrayList<>();

			for(int i = 0 ; i < K; i++){
				st = new StringTokenizer(br.readLine());

				int start = Integer.parseInt(st.nextToken());
				int end = Integer.parseInt(st.nextToken());
				int cost = Integer.parseInt(st.nextToken());
				int time = Integer.parseInt(st.nextToken());

				list[start].add(new Airport(end, cost, time));
			}         
			int result = dijkstra();
			sb.append(result == INF ? "Poor KCM\n" : result + "\n");
		}
        
		bw.write(sb.toString());
        
		bw.flush();
		bw.close();
		br.close();
	}

	public static int dijkstra() { 
		for(int i = 1 ; i < dp.length; i++)
			Arrays.fill(dp[i], INF);
        
		PriorityQueue<Airport> pqueue = new PriorityQueue<>();
		pqueue.add(new Airport(1, 0, 0));
		// 1번 노드까지 가는데 0 비용으로 갔을 때의 최소 시간
		dp[1][0] = 0;

		while(!pqueue.isEmpty()){
			Airport airport = pqueue.poll();
			int node = airport.end;
			int cost = airport.cost;
			int time = airport.time;

			if(node == N) break;
			if(dp[node][cost] < time) continue;
			dp[node][cost] = time;

			for(int i = 0 ; i < list[node].size(); i++){
				Airport toap = list[node].get(i);
				int toNode = toap.end;
				int toCost = cost + toap.cost;
				int toTime = time + toap.time;

				if(toCost > M) continue;
				if(dp[toNode][toCost] > toTime){
					for(int j = toCost; j <= M; j++){
						if(dp[toNode][j] > toTime) dp[toNode][j] = toTime;
					}
					pqueue.add(new Airport(toNode, toCost, toTime));
				}
			}
		}

		int result = Integer.MAX_VALUE;

		for(int i = 1; i <= M; i++)
			result = Math.min(result, dp[N][i]);
	
		return result;
	}
}

• Python

시간 초과 때문에 PyPy3로 했습니다..ㅠ

import sys
 
T = int(sys.stdin.readline())
INF = 2147483647
 
for _ in range(T):
    N, M, K=map(int,sys.stdin.readline().split()) # 공항 수,지원 비용,티켓정보 수
    ticket = [[] for _ in range(N+1)]
    for _ in range(K):
        u,v,c,d=map(int,sys.stdin.readline().split()) # 출발, 도착, 비용, 시간
        ticket[u].append([v,c,d])
 
    DP=[[INF]*(M+1) for _ in range(N+1)] # 열 : 비용 행 : n까지
    DP[1][0]=0
 
    for c in range(M+1):
        for d in range(1,N+1):
            if DP[d][c] == INF:continue # c의 비용으로 d에 도착하는 경우가 X
            t=DP[d][c] # c의 비용으로 d에 도착햇을때의 소요시간
            for dv,dc,dd in ticket[d]: # d에서 출발하는 모든 경우
                if dc+c > M:# 비용 초과 -> 넘어간다
                    continue
                DP[dv][dc+c]=min(DP[dv][dc+c],t+dd) #이전 값과 비교, 작으면 갱신
 
    result=min(DP[N]) # N 도착할때 최소 소요시간
 
    print("Poor KCM" if result == INF else result)