다익스트라
프로그래머스 2021 KAKAO BLIND RECRUITMENT Level 3 문제 합승 택시 요금을 Java를 이용해 풀어(?)보았다. 사실 다익스트라도 처음이고 가중치 그래프도 처음이라 그냥 공부하는 느낌이었다.
문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/72413
가중치 그래프 구현 및 탐색
이건 백준 1753번과 완전히 동일하기 때문에 여기를 참고해보기 바란다. 사실 합승 택시 요금을 풀려고 했더니 아는 게 하나도 없어서 참고가 될 만한 백준 문제를 먼저 풀어본 거다.
딱 하나 다른 거는 백준 1753번은 유방향 그래프였다면 이번 문제는 무방향 그래프라 이 부분만 한 줄 추가해주면 됐다.
합승 택시 비용 최솟값 구하기
1번부터 시작해서 모든 정점에 대해 다음을 수행해주면 된다.
s->k의 최소비용 +k->a의 최소비용 +k->b의 최소비용
위의 값을 계속 구하며 최솟값을 갱신해주면 결국 합승 택시 최소 비용을 구할 수 있다. 이를 코드로 표현하면 다음과 같다.
static Integer getCarPoolFee(int n, int s, int a, int b){
int min = Integer.MAX_VALUE;
for(int i=1; i<=n; i++){
min = Math.min(min, dist[s][i] + dist[i][a] + dist[i][b]);
}
return min;
}아래는 제출한 전체 코드다.
import java.util.ArrayList;
import java.util.PriorityQueue;
public class TaxiFee {
static int[][] dist;
static ArrayList<Node>[] edges;
static int solution(int n, int s, int a, int b, int[][] fares) {
int answer = 0;
/** 각 정점에 대한 최소 비용 배열 초기화 */
distInit(n);
/** 가중치 간선 정보 저장하기 */
edgesInit(n, fares);
/** 다익스트라 알고리즘 이용해서 모든 정점에 대해
* 자기 자신 제외한 다른 정점까지의 최소 비용 구하기 */
getDistance(n);
/** 합승할 경우 최소 비용 구하기 */
answer = getCarPoolFee(n,s,a,b);
return answer;
}
static void distInit(int n) {
dist = new int[n + 1][n + 1];
for (int i = 0; i < n + 1; i++)
for (int j = 0; j < n + 1; j++)
dist[i][j] = Integer.MAX_VALUE;
}
static void edgesInit(int n, int[][] fares){
edges = new ArrayList[n + 1];
for (int i = 0; i < n + 1; i++) edges[i] = new ArrayList<>(); // 초기화
for (int[] fare : fares) { // 간선 정보 저장하기
int start = fare[0];
int end = fare[1];
int weight = fare[2];
edges[start].add(new Node(end, weight));
edges[end].add(new Node(start, weight));
}
}
static void getDistance(int n){
for(int i=1; i<=n; i++){
dist[i][i] = 0; // 자기 자신에게 가는 비용은 당연히 0
PriorityQueue<Node> q = new PriorityQueue<>();
q.offer(new Node(i,0));
while(!q.isEmpty()){
Node cur = q.poll();
if(dist[i][cur.end] < cur.cost) continue; // 이미 최소비용이면 패스
for(int j=0; j<edges[cur.end].size(); j++){
Node next = edges[cur.end].get(j);
if(dist[i][next.end] > cur.cost + next.cost){
dist[i][next.end] = cur.cost + next.cost;
q.offer(new Node(next.end, cur.cost + next.cost));
}
}
}
}
}
static Integer getCarPoolFee(int n, int s, int a, int b){
int min = Integer.MAX_VALUE;
for(int i=1; i<=n; i++){
min = Math.min(min, dist[s][i] + dist[i][a] + dist[i][b]);
}
return min;
}
static class Node implements Comparable<Node> {
int end;
int cost;
Node(int end, int cost) {
this.end = end;
this.cost = cost;
}
@Override
public int compareTo(Node next) {
return this.cost - next.cost;
}
}
public static void main(String[] args) {
int n = 6;
int s = 4;
int a = 6;
int b = 2;
int[][] fares = {{4, 1, 10}, {3, 5, 24}, {5, 6, 2}, {3, 1, 41},
{5, 1, 24}, {4, 6, 50}, {2, 4, 66}, {2, 3, 22}, {1, 6, 25}};
int res = solution(n, s, a, b, fares);
System.out.println(res);
}
}오늘 배운 것
- 가중치 그래프는 간선 정보를 저장해줄 클래스 하나를 정의해서 List에 각 정점에 대한 간선 정보를 저장해주면 된다.
- 다익스트라 알고리즘은 동적 계획법을 이용해 하나의 노드로부터 도착점까지의 최소 비용을 구할 때 사용할 수 있다. 우선 순위 큐를 이용해 구현할 수 있다.
- 아직 멀었다...ㅠ
2022.03.08 재시도 ( 성공 )
다익스트라로 푸는 것은 이미 알고 있었기 때문에 다시 한 번 다익스트라 구현만 복습하고 풀어봤다. 처음에는 아무 생각 없이 int[] dist로 최소 비용 거리 배열을 1차원 배열로 선언했다가 나중에서야 dist[s][i]+dist[i][a]+dist[i][b]를 구해야 한다는 걸 깨닫고 다시 2차원 배열로 바꿨다. 출발점을 모든 지점에 대해서 한 번씩 돌려가며 int[][] dist를 업데이트 시켜주고나서 특정 지점을 거쳐 갈 때 드는 최소 비용을 구해줬다.
물론 코테를 앞두고 있을 때 주요 개념들에 대해서 한 번씩 복습은 해줘야겠지만 복습 시간을 줄일 수 있도록 제일 많이 나오는 알고리즘들에 대해서는 숙지해둬야겠다.
2023.02.01 재시도 ( 실패 )
1년 가까운 시간이 지난 후에 다시 풀어보니,,, 어렴풋이 기억이 나서 별로였다. 완전히 백지 상태로 다시 풀어보고 싶었는데 중간 과정을 거쳐가도록 식을 짜면 된다는 기억과 함께 다익스트라로 다시 풀었는데 효율성 테스트에서 4문제가 자꾸 통과되지 않았다.
결국 구글링을 하며 다시 공부해보았는데, 이 문제는 본질적으로 다익스트라가 아닌 플로이드 와샬 알고리즘이란 걸 이제서야 알았다. 다시 공부할 수 있게 되어 감사했다. 플로이드 와샬 알고리즘에 대해서는 전혀 몰랐는데 이번 기회에 새롭게 배우게 되었다.
오늘 배운 것
한 정점으로부터 나머지 모든 정점으로의 최소 비용 => 다익스트라 with 1차원 배열
모든 정점에 대해 나머지 정점들로의 최소 비용 => 플로이드 와샬 with 2차원 배열
이 정도만 숙지하고 있어도 쉽게 두 문제 유형을 구별할 수 있을 것 같다.
