[프로그래머스][2021 KAKAO BLIND RECRUITMENT][자바] 합승 택시 요금

programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

import java.io.*;
import java.util.*;

class Solution {
	public int solution(int n, int s, int a, int b, int[][] fares) {
		int answer = Integer.MAX_VALUE;
		int[][] map = new int[n][n];
		
		//초기화
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(i==j) map[i][j]=0;
				else map[i][j] = Integer.MAX_VALUE;
			}
		}
		
		for(int i=0; i<fares.length; i++) {
			map[fares[i][0]-1][fares[i][1]-1] = fares[i][2];
			map[fares[i][1]-1][fares[i][0]-1] = fares[i][2];
		}
		
		for(int k=0; k<n; k++) {
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					if(map[i][k] == Integer.MAX_VALUE || map[k][j] == Integer.MAX_VALUE) continue;
					map[i][j] = Math.min(map[i][j], map[i][k]+map[k][j]);
				}
			}
		}
		
		for(int i=0; i<n; i++) {
			answer = Math.min(answer, map[i][s-1]+map[i][a-1]+map[i][b-1]);
		}
		
		return answer;
	}

}

정리

• 경로를 거치고, 각 지점마다 최소 거리를 구하는 문제 이기때문에 플로이드 와샬로 풀면 쉽게 풀린다.
• 처음에 경로를 초기화 해준다.
• fares에서 값을 꺼내서 map 2차원 배열을 구성해준다.
• 플로이드 와샬로 알로기즘으로 각 노드의 최소값을 구한다.
• 각 지점별로 최고의 환승 지점을 찾는다.