문제

합승 택시 요금
두 사람(A와 B)이 같은 출발지 S에서 출발해서 각자의 목적지 A, B까지 이동해야 한다.
모든 지점 간 이동 비용이 주어진 그래프가 있을 때,

• 중간 지점까지 합승 후 갈라지기

• 혹은 아예 처음부터 따로 이동하기

이 둘 중 가장 비용이 적게 드는 경우의 총 택시요금을 구하는 문제.

풀이 접근

최소 거리를 구하는 그래프 문제이고, 합승 종료 지점 이라는 '중간 지점'이 있기 때문에,
모든 노드까지의 최단거리를 구하는 다익스트라 알고리즘이 적합하다고 생각했다.

나의 아이디어

문제에서 출발지는 A, B로 두 개이고
도착지점은 S로 하나이다.
그래서 도착지점 S에서 출발하여 A, B까지 가는 최소 비용을 각각 구하면 될 것이라고 생각했다.

아래와 같이 총 3번 다익스트라를 돌린다
1.s에서 모든 지점까지 최소 비용 배열 -> dist[]
2.s에서 A까지 최소 비용 구함 -> dist[]
3.s에서 A까지 최소 비용 구함 -> dist[]

그리고 합승하는 경우의 최소 비용과 따로 가는 경우의 최소 비용을 구한다음, 둘 중 작은 값을 구한다.

gpt 아이디어

gpt에게 물어보니 내가 설계한 것처럼 3번 다익스트라 배열을 만드는 것은 같지만, 결과를 훨씬 간단하게 구할 수 있다고 한다.

아래와 같이 총 3개의 다익스트라를 돌린다.
1.s에서 모든 지점까지 최소 비용 배열 -> dist[]
2.A에서 모든 지점까지 최소 비용 배열 -> dist[]
3.B에서 모든 지점까지 최소 비용 배열 -> dist[]

그리고 아래와 같이 K를 환승지점으로 돌리고 최소 비용을 구하면 끝이다.

answer = min( distS[k] + distA[k] + distB[k] )   for k = 1..n

정리하자면, 모든 점을 환승후보로 두고 최소 비용이 나오는 환승 지점을 구하면 된다.

코드로 정리하기

1.도착지점과 비용을 저장할 클래스 생성

비용이 작은 순서대로 정렬할 것이기 때문에 compareTo도 만들어 준다.

class Node implements Comparable<Node> {
	int to;
    int cost;
    
    Node (int to, int cost) {
    	this.to = to;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Node o){
    	return this.cost - o.cost;
    }
}

2. 그래프 생성하고 도착지점, 가격 저장하기

List<List<Node>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
	graph.add(new ArrayList<>());
}

//양방향으로 그래프 구성
for (int [] f : fares){
	int from = f[0];
    int to = f[1];
    int cost = f[2];
    
    graph.get(from).add(new Node(to, cost)));
    graph.get(to).add(new Node(from, cost)));
}

3. 다익스트라 함수 생성하기

private int[] dijkstra(int strat, int n, List<List<Node>> graph){
	//우선순위 큐 생성
  	PriorityQueue<Node> pq = new PriorityQueue<>();
    //최소 거리를 저장할 거리 배열 생성
    int[] dist = new int[n + 1];
    //초기값을 최대값으로 채우기
    Arrays.fill(dist.INF);
    //시작지점의 거리는 0으로
    dist[start] = 0;
    //시작지점의 객체 넣기 
    pq.offer(new Node(start, 0));
    
    while(!pq.isEmpty()){
    	Node now = pq.poll();
        //현재의 값이 배열에 저장된 값보다 크면 넘어가기
        //now.cost : 현재 지점에서 now.to까지의 비용 (바로 이어진 경우의 비용)
        //dist[now.to] : 배열에 저장된 비용
        if (now.cost > dist[now.to]) continue;
        
        //현재 지점과 연결된 모든 지점을 탐색하기
        for (Node next : graph.get(now.to)){
        //현재까지 오는 데 든 비용 + 인접 노드로 가는 비용 = 새로운 후보 비용
        	int newCost = now.cost + next.cost;
            //만약 현재 알고 있는 최단거리보다 새로 계산한 비용이 더 작다면
            if (newCost < dist[next.to]){
            //최단 거리 업데이트를 한다.
            	dist[next.to] = newCost;
                pq.offer(new Node(next.to, newCost));
            }
        }
    }
    return dist;
  }

4. 가장 비용이 싼 합승 지점 탐색하기

    int[] distS = dijkstra(s, n, graph);
      int[] distA = dijkstra(a, n, graph);
      int[] distB = dijkstra(b, n, graph);

      int answer = INF;

      // 중간 합승 지점 k(1~n) 탐색
      for (int k = 1; k <= n; k++) {
          long total = (long)distS[k] + distA[k] + distB[k];
          answer = (int)Math.min(answer, total);
      }

      return answer;

다익스트라 정리

이 문제를 풀면서 다익스트라를 완전히 이해하지 못했다는 것을 깨닫고... 코드 흐름을 다시 정리해보았다.
다익스트라 정리

전체 코드

import java.util.*; //import 써주기

class Node implements Comparable<Node>{
  int to;
  int cost;
  
  public Node(int to, int cost) {
      this.to = to;
      this.cost = cost;
  }
  
  @Override
  public int compareTo(Node o) {
      return this.cost - o.cost;
  }
}


class Solution {
  static final int INF = Integer.MAX_VALUE; //이것도 체크
  static List<List<Node>> graph;
  static int N;
  
  public int solution(int n, int s, int a, int b, int[][] fares) {
      N = n;
      
      graph = new ArrayList<>();
      for (int i = 0; i <= n; i ++) {
          graph.add(new ArrayList<>());
      }
      
      for (int i = 0; i < fares.length; i++) {
          int from = fares[i][0];
          int to = fares[i][1];
          int cost = fares[i][2];
          graph.get(from).add(new Node(to, cost));
          graph.get(to).add(new Node(from, cost));
      }
      
      //s -> 모든 지점의 최단거리 
      //a -> 모든지점
      //b -> 모든 지점
      int[] dist_s = dijstra(s);
      int[] dist_a = dijstra(a);
      int[] dist_b = dijstra(b);
      
      int min_fare = INF;
      for (int k = 1; k <= n ; k ++) {
          min_fare = Math.min(min_fare, dist_s[k] + dist_a[k] + dist_b[k]);
      }

      return min_fare;
  }
  
  //start에서 모든 지점까지의 최소거리
public int[] dijstra(int start) {
  PriorityQueue<Node> pq = new PriorityQueue<>();
  int[] dist = new int[N + 1];
  Arrays.fill(dist, INF); //이것도 확인 Array.를 써야 한다
  dist[start] = 0;
  pq.offer(new Node(start, 0));
  
  while(!pq.isEmpty()) {
      Node curr = pq.poll();
      if (curr.cost > dist[curr.to]) continue;
      
      for (Node next : graph.get(curr.to)) {
          int new_cost = curr.cost + next.cost;
          if (new_cost < dist[next.to]) { //조건을 걸어서 만족할 경우에만 큐에 넣어야 함
              dist[next.to] = new_cost;
              pq.offer(new Node(next.to, new_cost));
          }
      }
  }
  return (dist);
}


  
}