문제 주소
https://school.programmers.co.kr/learn/courses/30/lessons/72413
풀이 과정
1차시도 - DFS
어쨌든 경로를 순회하면서 최소비용을 찾아야 하므로 DFS를 사용해서 노드를 모두 순회했다.
노드를 순회할때는 출발지점에서 임의의 지점까지 이동한 후, 그 지점에서 a, b 지점으로 가기 위한 dfs를 각각 수행했다.
import java.util.*;
class Solution {
public int solution(int n, int s, int a, int b, int[][] fares) {
Node[] graph = new Node[n];
for(int[] fare : fares){
int p1 = fare[0];
int p2 = fare[1];
if(graph[p1 - 1] == null){
graph[p1 - 1] = new Node(p1, n);
}
if(graph[p2 - 1] == null){
graph[p2 - 1] = new Node(p2, n);
}
Node n1 = graph[p1 - 1];
Node n2 = graph[p2 - 1];
n1.map.put(n2, fare[2]);
n2.map.put(n1, fare[2]);
}
return together(graph[s - 1], a, b, graph);
}
private int together(Node node, int a, int b, Node[] graph){
if(node.num == a && node.num == b) return 0;
node.visited = true;
int min = Integer.MAX_VALUE;
int minA = Integer.MAX_VALUE;
int minB = Integer.MAX_VALUE;
Set<Node> set = node.map.keySet();
for(Node n : set){
if(n.visited) continue;
int nCost = node.map.get(n);
if(nCost > min) continue;
if(node.num != a && node.num != b) {
int cost = nCost + together(n, a, b, graph);
if(cost > 0 && cost < min) min = cost;
}
if(node.num != a){
int cost = nCost + alone(n, a, graph);
if(cost > 0 && cost < minA) minA = cost;
} else minA = 0;
if(node.num != b){
int cost = nCost + alone(n, b, graph);
if(cost > 0 && cost < minB) minB = cost;
} else minB = 0;
}
if(minA + minB > 0 && minA + minB < min) min = minA + minB;
node.visited = false;
return min;
}
private int alone(Node node, int a, Node[] graph){
if(node.num == a) return 0;
int min = Integer.MAX_VALUE;
node.visited = true;
Set<Node> set = node.map.keySet();
for(Node n : set){
if(n.visited) continue;
int nCost = node.map.get(n);
if(nCost > min) continue;
int cost = nCost + alone(n, a, graph);
if(cost > 0 && cost < min) min = cost;
}
node.visited = false;
return min;
}
private class Node{
int num;
boolean visited;
Map<Node, Integer> map = new HashMap<>();
int[] dist;
public Node(int num, int n){
this.num = num;
this.dist = new int[n];
}
}
}위 코드에서 together는 택시를 같이 타고 이동하는 경우를 탐색하는 메서드이고, alone은 각각 타고 이동하는 경우를 탐색하는 메서드이다. 두 메서드 모두 노드를 순회하면서, 각 노드간 비용을 더해가면서 비용의 최소값을 반환한다.
중간에 택시 비용의 최소값을 갱신하는 부분에 cost > 0이 있는데 이는 오버플로우가 발생하는 상황을 제외하기 위함이다.
위 코드는 정확성 테스트를 모두 통과했지만, 효율성 테스트를 모두 실패했다.
2차 시도 - Dijkstra
어떻게 효율을 해결해야 할지 고민하다가, 해당 문제에 질문 목록에 들어갔는데, 글 제목에 다익스트라가 보여서 다익스트라에 대해 검색을 통해 공부해보기로 했다. 다익스트라에 대해서는 그래프를 탐색하는 알고리즘이라는 것 정도만 알고 있었다.
다익스트라에 대해 간단하게 설명하자면, 가중치(음수가 아닌 경우)가 존재하는 그래프에서 하나의 노드에서 다른 노드로 가는 최단 경로를 구하는 알고리즘이다. 만약 각각의 노드에서 다른노드로 가는 최단 경로를 모두 구하고 싶다면 각각의 노드에 다익스트라를 적용해야 한다.
다익스트라 알고리즘의 과정은 다익스트라를 적용할 노드를 source라고 하면
1. source에서 바로 이어져 있는 노드들까지의 거리를 기록한다.
2. 기록된 노드중 가장 가까운 노드로 이동한다.
3. 이동한 노드에 연결된 노드들을 탐색한다. 이동한 노드를 거쳐서 갈 경우 기존보다 짧은 거리로 갈 수 있는 경우(또는 갈수 없었던 노드를 갈 수 있는 경우) source부터 해당 노드 까지의 거리를 갱신한다.
4. 이동했던 노드는 더이상 탐색하지 않는 노드로 기록한다.(가장 가까운 노드를 택했으므로 다른 노드를 거쳐서 가면 무조건 손해이다. 따라서 더이상 탐색하지 않는다.)
5. 남은 노드중 source에서 가장 가까운 노드로 이동한다.
6. 3~4를 반복한다.
위 과정이다.
DFS와 달리 모든 경우의 수를 탐색하지 않고, 가장 가까운 노드부터 탐색해서 더이상 탐색할 필요가 없는 노드를 탐색하지 않으므로 효율성이 크게 개선된다.
최종 코드
class Solution {
int[][] matrix;
public int solution(int n, int s, int a, int b, int[][] fares) {
matrix = new int[n][n];
Node[] graph = new Node[n];
int result = Integer.MAX_VALUE;
for(int i = 0; i < n; i++){
graph[i] = new Node(i + 1, n);
}
for(int[] fare : fares){
int p1 = fare[0];
int p2 = fare[1];
Node n1 = graph[p1 - 1];
Node n2 = graph[p2 - 1];
n1.addNode(n2, fare[2]);
}
for(Node node : graph){
dijkstra(graph, node);
}
for(Node node : graph){
int cost = node.dist[s - 1] + node.dist[a - 1] + node.dist[b - 1];
if(result > cost) result = cost;
}
return result;
}
private void dijkstra(Node[] graph, Node source){
int length = graph.length;
for(int i = 0; i < length - 1; i++){
int idx = getClose(source);
if(idx == -1) break;
boolean[] visited = source.visited;
visited[idx] = true;
for(int j = 0; j < length; j++){
if(visited[j]) continue;
if(matrix[idx][j] > 0 && source.dist[j] > source.dist[idx] + matrix[idx][j]){
source.dist[j] = source.dist[idx] + matrix[idx][j];
}
}
}
}
private int getClose(Node source){
int min = Integer.MAX_VALUE;
int[] dist = source.dist;
int length = dist.length;
int result = -1;
for(int i = 0; i < length; i++){
if(dist[i] < min && !source.visited[i]){
result = i;
min = dist[i];
}
}
return result;
}
private class Node{
int num;
boolean[] visited;
int[] dist;
Node[] prev;
public Node(int num, int n){
this.num = num;
this.visited = new boolean[n];
this.dist = new int[n];
this.prev = new Node[n];
for(int i = 0; i < n; i++){
dist[i] = Integer.MAX_VALUE / 4;
}
dist[num - 1] = 0;
visited[num - 1] = true;
}
public void addNode(Node node, int d){
this.dist[node.num - 1] = d;
node.dist[this.num - 1] = d;
matrix[this.num - 1][node.num - 1] = d;
matrix[node.num - 1][this.num - 1] = d;
}
}
}dijkstra()는 다익스트라를 수행하는 메서드이며, getClose()는 source에서 탐색하지 않는 노드중 가장 가까운 노드를 반환하는 메서드이다.
다익스트라로 각 노드에서 다른노드로 가는 최단거리를 구한 후에는, 각 노드마다 (s로 가는 거리 + a로 가는 거리 + b로 가는 거리)를 구했다. 결국 이문제에서 택시를 타고 가는 경로는 s에서 같이 출발해서 어느 지점(분기점)까지는 같이 가고, 분기점 부터는 각자 a, b로 가는 경로인데 이때 이동 거리의 총합은 (분기점에서 s로 가는 거리 + 분기점에서 a로 가는 거리 + 분기점에서 b로 가는 거리)가 되기 때문에 결국 노드마다 이 거리들의 합을 구해서 최소값을 반환하면 된다.
dist[i]의 기본값을 Integer.MAX_VALUE / 4로 한것은 오버플로우를 방지하기 위함이다.
위 코드는 정확성 테스트와 효율성 테스트를 모두 통과했다.
