[Programmers/72413/JAVA] 합승 택시 요금

날짜	분류	번호	알고리즘 분류
21-03-25	프로그래머스	72413	다익스트라	링크

문제 요약

1. S에서 A와 B로 가는 최소 비용
2. 같은 곳을 지나친다면 합승해서 함께 감

 

풀이

1. S로부터 모든 지점까지의 거리를 다익스트라로 계산
   • A와 B도 마찬가지
2. S, A, B로부터 거리를 저장한 배열 3개를 가지고 어느 점까지가 최소 거리인지 반복문을 돌려서 찾음

 

비고

• 처음에는 모든 점에 대해서 다익스트라를 구해서 S까지거리+A까지거리+B까지거리를 찾았는데 시간초과가 났음

 

 

package KakaoBlindRecruitment2021.P72413_합승택시요금;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {

	static final int INF = Integer.MAX_VALUE;

	// 지금: 한점에서 S까지 + A까지 + B까지
	// => S부터 모든 거리, A부터 모든 거리 , B부터 모든 거리 다 구해서 합이 최소인 점 찾기
	// 더 빨라질듯
	public static int solution(int n, int s, int a, int b, int[][] fares) {
		int answer = INF;

		List<Node>[] adj = new ArrayList[n + 1];
		for (int i = 1; i <= n; i++)
			adj[i] = new ArrayList<>();

		for (int i = 0; i < fares.length; i++) {
			int src = fares[i][0];
			int dest = fares[i][1];
			int c = fares[i][2];
			adj[src].add(new Node(dest, c));
			adj[dest].add(new Node(src, c));
		}

		int[][] cost = new int[3][n + 1];
		dijkstra(cost[0], n, s, adj);
		dijkstra(cost[1], n, a, adj);
		dijkstra(cost[2], n, b, adj);

		for (int i = 1; i <= n; i++) {
			int sum = 0;
			for (int j = 0; j < 3; j++) {
				sum += cost[j][i];
			}
			answer = Math.min(answer, sum);
		}

		return answer;
	}

	static void dijkstra(int[] cost, int n, int start, List<Node>[] adj) {

		for (int i = 1; i <= n; i++) {
			cost[i] = INF;
		}

		Queue<Node> pq = new PriorityQueue<>();
		boolean[] visit = new boolean[n + 1];

		cost[start] = 0;
		pq.add(new Node(start, cost[start]));

		for (int step = 0; step < n; step++) {
			Node cur = pq.poll();

			while (cur != null && visit[cur.no])
				cur = pq.poll();

			if (cur == null)
				break;

			visit[cur.no] = true;

			for (int i = 0; i < adj[cur.no].size(); i++) {
				Node target = adj[cur.no].get(i);
				if (visit[target.no])
					continue;
				if (cost[target.no] > target.c + cur.c) {
					cost[target.no] = target.c + cur.c;
					pq.add(new Node(target.no, target.c + cur.c));
				}
			}

		}
	}

	static class Node implements Comparable<Node> {
		int no, c;

		public Node(int no, int c) {
			super();
			this.no = no;
			this.c = c;
		}

		@Override
		public int compareTo(Node o) {
			return this.c - o.c;
		}

	}

	public static void main(String[] args) {

	}

}