합승 택시 요금(Lv.3)

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

모든 지점을 하차지점으로 생각했을 때 각 지점에서 출발점(S), A, B 까지의 거리 중 최소값 구하기

 

---

 

풀이

 

접근 방식

1. 최소 비용 구하기

  → 간선의 가중치가 1이 아니기 때문에 다익스트라 알고리즘을 통해 최소 비용 구하기

 

2. 하차지점 설정

  → 합승을 했다면 반드시 하차지점이 생기고, 하차지점으로 부터 출발점, A도착점, B도착점까지의 거리를 계산한다.

  → 하차지점은 출발점(S)~하차지점, 하차지점~A, 하차지점~B 세 구간을 더한 값이 최소가 되는 노드로 설정한다.

  → 하차지점을 구하기 위해 모든 노드에 대해서 다익스트라 알고리즘을 실행한다.

 

---

 

코드리뷰

 

import java.util.*;

// 인접 노드 번호와 간선의 가중치를 저장하기 위한 객체 클래스
class Node {
    int index;	// 인접 노드 번호
    int cost;	// 간선의 가중치
    public Node(int index, int cost) {
        this.index = index;
        this.cost = cost;
    }
}

class Solution {
    int n;
    ArrayList<Node>[] graph;	// 각 노드에 대한 인접 노드 리스트를 담을 배열
    int[] dist;	// 각 노드에 대한 최소 비용을 담을 배열
    boolean[] visited;	// 방문 여부를 체크하기 위한 배열
    
    // 최소 비용을 구하는 다익스트라 알고리즘 메소드
    public void dijkstra(int start) {
        visited = new boolean[n+1];	// 각 노드에 대해 반복해서 실행되므로 메소드 내부에서 초기화 진행
        dist = new int[n+1];	// 마찬가지로 메소드 내부에서 초기화
        Arrays.fill(dist, Integer.MAX_VALUE);	// 초기 값은 MAX_VALUE로 설정
        dist[start] = 0;	// 출발점까지의 거리는 0으로 설정
        
        // 우선순위 큐를 활용해서 가중치가 작은 순으로 방문
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        pq.add(new Node(start, 0));	// 시작 지점은 0으로 설정
        
        while(!pq.isEmpty()) {
            int nowIndex = pq.poll().index;	// 간선의 가중치가 가장 작은 노드를 방문
            if(visited[nowIndex]) continue;	// 방문했다면 건너 뜀
            visited[nowIndex] = true;	// 방문했음을 표시
            for(Node adj : graph[nowIndex]) {	// 방문한 노드의 인접 노드들에 대해
                if(dist[adj.index] > dist[nowIndex] + adj.cost) {	// 기본으로 설정한 MAX_VALUE와 현재까지의 거리 + 인접노드의 간선의 가중치를 비교
                    dist[adj.index] = dist[nowIndex] + adj.cost;	// 더 작은 값으로 해당 노드까지의 거리 설정
                    pq.add(new Node(adj.index, dist[adj.index]));	// 인접 노드들을 모두 우선순위 큐에 담는다.
                }
            }
        }
    }
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        // n: 노드 개수, s: 시작위치, a: A가 내리는 노드, b: B가 내리는 노드
        this.n = n;
        graph = new ArrayList[n+1];	// 인접 노드 리스트를 담을 배열
        List<Integer> list = new ArrayList<>();
        
        for(int i = 0; i < graph.length; i++)
            graph[i] = new ArrayList<>();	// 인접 노드 리스트 초기화
        for(int[] arr : fares) {
            int u = arr[0];
            int v = arr[1];
            int cost = arr[2];
            graph[u].add(new Node(v, cost));	// 간선의 방향은 없으므로
            graph[v].add(new Node(u, cost));	// 양쪽 모두 번갈아 담기
        }
        for(int i = 1; i <= n; i++) {	// 각 노드에 대해 다익스트라 알고리즘 실행
            dijkstra(i);
            // 각 노드를 하차지점으로 했을 때 합승 택시 요금 계산
            // 여기엔 출발점(S)도 포함되기 때문에 출발점에서 각자 가는 경우도 계산됨(출발점~출발점까지는 0이기 때문)
            list.add(dist[a] + dist[b] + dist[s]);	// dist[a]: 하차지점~A, dist[b]: 하차지점~B, dist[s]: 출발점(S)~하차지점
        }
        return Collections.min(list);	// 최소값 리턴
    }
}

 

---

 

추가 자료

 

특정 노드까지의 최단 경로 출력

public List<Integer> getSpath(int i) {	// 매개변수 i는 종착점
    List<Integer> list = new ArrayList<>();	// 경로를 담을 리스트
    int curr = i;
    while(curr != -1) {	// curr == -1 이라는 것은 해당 노드는 최단 경로에 포함되지 않음을 의미
        list.add(curr);	// 첫 번째로는 마지막 노드인 종착점을 추가
        curr = history[curr];	// history[curr]: 시작 노드부터 <curr 노드>까지 최단 거리를 갱신했을 때의 nowIndex
    }
    return list;
}

 

 

사용 예시

import java.util.*;

class Solution {
	(...)
    int[] history = new int[n+1]	// 경로를 담을 배열
    
    public void dijkstra(int start) {
    	(...)
        Arrays.fill(history, -1);	// 경로 배열을 -1로 초기화
        
        while(!pq.isEmpty()) {
            (...)
            for(Node adj : graph[nowIndex]) {
                if(dist[adj.index] > dist[nowIndex] + adj.cost) {
                    dist[adj.index] = dist[nowIndex] + adj.cost;	// 최단 거리가 갱신되었다면
                    history[adj.index] = nowIndex;	// 해당 인접 노드의 마지막 경로로 현재 노드를 추가
                    (...)
                }
            }
        }
    }
    
    public List<Integer> getSpath(int i) {
        List<Integer> list = new ArrayList<>();
        int curr = i;
        while(curr != -1) {
            list.add(curr);
            curr = history[curr];
        }
        return list;
    }
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        (...)
        // 특정 노드(여기선 출발점 s)에 대해 다익스트라 알고리즘을 실행하고
        dijkstra(s);
        // 특정 노드로 부터 최단 경로를 출력하고 싶은 노드(여기선 3번 노드)를 getSpath() 메소드의 인자로 넘겨준다.
        List<Integer> spList = = getSpath(3);
        (...)
    }
}

 

history 배열에는 출발점(4번 노드)으로 부터 각 노드에 대한 최단 거리를 갖는 인접노드가 담김