문제
풀이
BFS와 DP를 활용하는 문제였다.
중간에 환승이 끝나는 지점인 shared를 기준으로, 세 구간의 비용의 합인 dp[start][shared] + dp[shared][a] + dp[shared][b]가 최솟값이 되는 경우를 찾아야 한다. dp에 활용되는 모든 경우의 수를 고려하기 위해 s, a, b를 각각 출발점으로 하는 모든 경로를 탐색해야 한다.
각각의 경로를 탐색할 때는 Queue를 활용한 BFS를 적용한다. 각각의 구간에서 최솟값인 경우에만 계속 BFS를 확장해가며 dp에 최소경로비용을 저장해놓는다.
그리고 마지막으로 shared가 없는 경우부터, 각각의 지점이 shared가 되는 경우를 모두 고려한 minCost를 찾아 답으로 반환한다.
내가 스스로 생각해내지 못한 부분은, s, a, b를 시작점으로 해서 dp를 갱신하는 부분이다. 어떻게 해야 모든 경로를 탐색할 수 있는지 아무리 고민해도 떠오르지 않았다. 답을 보고 나면 이해가 바로 되는데 왜 스스로 생각해내는 건 못하는지ㅠㅠ 더 다각적으로 생각해보는 습관을 가져보자...
코드
import java.util.*;
class Solution {
private static final int MAX = 200;
private List<List<Integer>> graph = new ArrayList<>();
private int[][] costs = new int[MAX + 1][MAX + 1];
private int[][] dp = new int[MAX + 1][MAX + 1];
public int solution(int n, int s, int a, int b, int[][] fares) {
parseFares(n, fares);
calcMinCost(s);
calcMinCost(a);
calcMinCost(b);
int minCost = dp[s][a] + dp[s][b];
for (int shared = 1; shared <= n; shared++) {
if (dp[s][shared] == Integer.MAX_VALUE || dp[shared][a] == Integer.MAX_VALUE || dp[shared][b] == Integer.MAX_VALUE)
continue;
minCost = Math.min(minCost, dp[s][shared] + dp[shared][a] + dp[shared][b]);
}
return minCost;
}
private void parseFares(int n, int[][] fares) {
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
Arrays.fill(dp[i], Integer.MAX_VALUE);
dp[i][i] = 0;
}
for (int[] fare : fares) {
int start = fare[0], end = fare[1], cost = fare[2];
graph.get(start).add(end);
graph.get(end).add(start);
costs[start][end] = cost;
costs[end][start] = cost;
}
}
private void calcMinCost(int start) {
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(start, 0));
while (!queue.isEmpty()) {
Node current = queue.poll();
for (int nextPosition : graph.get(current.position)) {
int nextCost = current.cost + costs[current.position][nextPosition];
if (dp[start][nextPosition] > nextCost) {
dp[start][nextPosition] = nextCost;
dp[nextPosition][start] = nextCost;
queue.offer(new Node(nextPosition, nextCost));
}
}
}
}
}
class Node {
int position;
int cost;
public Node(int position, int cost) {
this.position = position;
this.cost = cost;
}
}