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

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

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

class Solution {
		public int solution(int n, int s, int a, int b, int [][] fares) {
			int answer=Integer.MAX_VALUE;
			
			int cost[][]= new int[n+1][n+1];
			
			for(int i=0; i<fares.length; i++) {
				int []fare = fares[i];
				cost[fare[0]][fare[1]]=fare[2];
				cost[fare[1]][fare[0]]=fare[2];
			}
			
			//최소비용으로 갱신 
			for(int k=1; k<=n; k++) {
				for(int i=1; i<=n; i++) {
					for(int j=1; j<=n; j++) {
						if(i==j || cost[i][k]==0 || cost[k][j]==0) continue;
						if(cost[i][j]==0) cost[i][j]=cost[i][k]+cost[k][j];
						else cost[i][j]=Math.min(cost[i][j], cost[i][k]+cost[k][j]);
					}
				}
			}
			
			for(int i=1; i<=n; i++) {
				if(cost[s][i]+cost[i][a]+cost[i][b]==0 ) continue;
				answer=Math.min(cost[s][i]+cost[i][a]+cost[i][b], answer);
			}
			
			return answer;

		}
	}

소요시간 : 35분

 

전형적인 플루이드-와샬 문제입니다!

 

모든 꼭지점 사이에 거리를 구해야 하기 때문에 문제를 보자마자 플루이드-와샬이라고 생각했습니다.

 

n의 크기또한 200이하이기 때문에 3중포문을 돌려도 괜찮다고 생각했습니다.

 

우선 로직을 살펴보면

 

1. 플루이드 - 와샬을 통해 모든 지점을 최소비용으로 갱신해줍니다. ( k : 경유, i :출발, j : 도착)

 

2. 모든 꼭지점을 돌면서 i지점에서 내렸을 때 i->a, i->b 까지의 비용을 구해서 answer을 구해줍니다!