[코틀린, 자바] 프로그래머스 lv3 : 합승 택시 요금 (카카오 기출문제 풀이)

문제 풀러 가기!

풀이

최단거리 문제입니다. 다익스트라로 해결하였습니다.

이 문제에서 중요한 것은 A와 B는 특점 지점까지만 합승하고 남은 길은 따로 가는것이 포인트입니다. 그러나 역으로 생각해보면 S, A, B 각각의 지점이 특점 지점까지 모이는 거리와 같은 의미가 됩니다.

만약 위 그림과 같이 2 지점까지만 합승하고 A와 B는 따로 가는것이 최단거리라 가정해봅시다.

이 것은 결국 S, A, B 각각의 지점에서 2지점까지 가는 최소거리들의 합 이 됩니다.

코드 올려드리겠습니다.

Source Code

코틀린

package Kakao_Blind_Recruitment_2021.합승_택시_요금

import java.util.*
import kotlin.math.*
const val INF = 1_000_000_000

class Solution {
    private lateinit var dst: IntArray
    private lateinit var list: Array<ArrayList<Node>>
    fun solution(n: Int, s: Int, a: Int, b: Int, fares: Array<IntArray>): Int {
        var answer: Int = Integer.MAX_VALUE
        list = Array(n + 1) { ArrayList<Node>() }

        // 인접리스트 채우기
        for (i in fares.indices) {
            val (start, end, weight) = fares[i].map { it }

            list[start].add(Node(end, weight))
            list[end].add(Node(start, weight))
        }
        val dstS = dijkstra(s, n)
        val dstA = dijkstra(a, n)
        val dstB = dijkstra(b, n)

        for (i in 1 .. n) {
            // 갈 수 없는 곳이면 continue
            if (dstS[i] == INF || dstA[i] == INF || dstB[i] == INF) continue
            // S, A, B 각각 i지점까지 오는 최단거리는 i지점까지 합승하고 A, B 따로 가는 거리와 같다.
            answer = min(answer, dstS[i] + dstA[i] + dstB[i])
        }
        return answer
    }
    fun dijkstra(start: Int, n: Int): IntArray {
        val q = PriorityQueue<Node>()
        val isVisited = BooleanArray(n + 1)
        dst = IntArray(n + 1) {i -> INF}
        dst[start] = 0
        q.offer(Node(start, 1))

        while (q.isNotEmpty()) {
            val cur = q.poll()
            if (isVisited[cur.end]) continue
            isVisited[cur.end] = true

            for (next in list[cur.end]) {
                if (dst[next.end] > dst[cur.end] + next.weight) {
                    dst[next.end] = dst[cur.end] + next.weight
                    q.offer(Node(next.end, dst[next.end]))
                }
            }
        }
        return dst
    }
}
data class Node(val end: Int, val weight: Int) : Comparable<Node> {
    override fun compareTo(other: Node) = weight - other.weight
}

자바

import java.util.*;

class Solution {
    static ArrayList<Node>[] list;
    static int n, s, a, b, fares[][];
    static int[] dst;
    static boolean[] isVisited;
    static final int INF = Integer.MAX_VALUE;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        this.n = n; this.s = s; this.a = a; this.b = b; this.fares = fares;
        list = new ArrayList[n + 1];
        for (int i = 0 ; i <= n ; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i = 0 ; i < fares.length ; i++) {
            int start = fares[i][0];
            int end = fares[i][1];
            int weight = fares[i][2];
            
            list[start].add(new Node(end, weight));
            list[end].add(new Node(start, weight));
        }
        int min = Integer.MAX_VALUE;
        
        int[] Sdst = dijkstra(s);
        int[] Adst = dijkstra(a);
        int[] Bdst = dijkstra(b);
        
        for (int i = 1 ; i <= n ; i++) {
            min = Math.min(Sdst[i] + Adst[i] + Bdst[i], min);
        }
        
        
        return min;
    }
    static int[] dijkstra (int start) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        isVisited = new boolean[n + 1];
        dst = new int[n + 1];
        Arrays.fill(dst, INF);
        q.offer(new Node (start, 0));
        dst[start] = 0;
        
        while (!q.isEmpty()) {
            Node d = q.poll();
            
            if (isVisited[d.end]) continue;
            isVisited[d.end] = true;
            
            for (Node next : list[d.end]) {
                if (!isVisited[next.end] && dst[next.end] > dst[d.end] + next.weight) {
                    dst[next.end] = dst[d.end] + next.weight;
                    q.offer(new Node(next.end, dst[next.end]));
                }
            }
        }
        return dst;
    }
}
class Node implements Comparable<Node>{
    int end;
    int weight;
    Node(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}