12913번: 매직 포션

• N개의 도시가 있고 모두 연결되어 있다 (2 ≤ N ≤ 50).
• K개의 매직 포션을 가지고 있다 (0 ≤ K ≤ 50).
• 매직 포션은 도시 간 이동 시간을 절반으로 줄여준다.
• 각 도시 간 이동 시간은 0 이상 9 이하의 수이다.
• 도시 0에서 도시 1로 가는 가장 빠른 시간을 구해야 한다.
• 모든 매직 포션을 다 사용할 필요는 없다.

접근

가장 빠른 시간 구하기

가장 빠른 도달 시간 = 최단 경로 문제
최단 경로 문제이면서 경로가 그래프로 이루어져있기 때문에 다익스트라 알고리즘을 생각해볼 수 있다.

매직 포션과 방문 처리

1. 포션 개수 추적
   횟수가 제한된 포션을 사용하여 경로를 단축시킬 수 있다.
   다익스트라를 통해 최단 경로를 찾아가면서 사용된 포션의 개수도 추적해야한다.
   도시에 도달하기 위한 경로가 포션을 K, K-1, ... , 0개 사용했을 때의 경우 모두 다르기 때문이다.

2. 도시의 방문 처리
   사용가능한 포션 개수를 저장했다면, 효율적인 탐색을 위해 도시의 방문 처리가 필요하다.
   현재 포션 개수와 도시로 이루어진 이차원 배열을 활용해 k개의 포션을 보유했을 때 n번째 도시에 도달한 경우가 있는지 확인하는 것이다.
   배열의 크기가 최대 [50][50]이기 때문에 메모리 공간의 걱정도 없다.
   또한, 갱신되는 int배열이 아닌 한번만 체크되는 boolean 배열을 사용하는 이유는 다익스트라 알고리즘에 의해 k개의 포션을 가지고 n번째 도시에 도달하는 최단 경로가 먼저 탐색되기 때문이다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        
        input(in);
        solve();
    }
    
    static int nCity;
    static int nPotion;
    static float[][] time;
    static void input(BufferedReader in) throws IOException {
    	StringTokenizer tokens = new StringTokenizer(in.readLine());
    	nCity = Integer.parseInt(tokens.nextToken());
    	nPotion = Integer.parseInt(tokens.nextToken());
    	
    	time = new float[nCity][nCity];
    	
    	for(int i = 0; i < nCity; i++) {
    		char[] line = in.readLine().toCharArray();
    		for(int j = 0; j < nCity; j++) {
    			time[i][j] = Character.getNumericValue(line[j]);
    		}
    	}
    }
    
    static void solve() {
    	boolean[][] visited = new boolean[nPotion+1][nCity];
    	
    	PriorityQueue<Path> pq = new PriorityQueue<Path>();
    	
    	pq.add(new Path(0, nPotion, 0f));
    	
    	while(!pq.isEmpty()) {
    		Path cur = pq.poll();
    		
    		if(visited[cur.potions][cur.dest]) continue;
    		visited[cur.potions][cur.dest] = true;
    		
    		if(cur.dest == 1) {
    			System.out.println(cur.time);
    			break;
    		}
    		
    		for(int i = 0; i < nCity; i++) {
    			if(i == cur.dest) continue;
    			
    			// Use potion
    			if(cur.potions > 0 && !visited[cur.potions-1][i]) {
    				pq.add(new Path(i, cur.potions-1, cur.time + time[cur.dest][i]/2f));
    			}
    			
    			// Not use potion
    			if(!visited[cur.potions][i]) {
    				pq.add(new Path(i, cur.potions, cur.time + time[cur.dest][i]));
    			}
    		}
    	}
    }
    
    static class Path implements Comparable<Path>{
    	int dest;
    	int potions;
    	float time;
    	
    	public Path(int d, int p, float t) {
    		dest = d;
    		potions = p;
    		time = t;
    	}
    	
    	public int compareTo(Path other) {
    		return Float.compare(time, other.time);
    	}
    }
}

회고

• 최단 경로를 찾는 다익스트라 알고리즘에 제한된 횟수의 경로 단축을 사용하는 문제.
• 소수점 계산이 문제가 될 수 있지만, 문제에서 주어지는 제한이 널널해서 소수점 오류가 문제가 되지 않는다.