[프로그래머스 , Java] Level3: 합승 택시 요금

 

문제분석:

 

문제 목표:  두 사람이  Start 지점으로부터 A와 B로 가려고합니다.  

하지만 두 사람은  이동 경로가 비슷 하다면 합승을 할 수 있습니다.  

 

합승을 한다면,  합승한 경로만큼 택시비가 안들어갑니다.  

 

그러므로,  A와 B의 택시비가 최소로 나오는 택시비를 구해주세요.

 

 

 

이 문제는  Level4는 줘야하지 않나...

 

그 이유는 특수알고리즘의 지식 때문이다.  

뭐.. 해당 문제를 처음부터 끝까지 코딩을 할수야 있겠지만, 어설프게 코딩을 치다간 

놓치는 케이스와 효율성때문에  즉시 에러를 뱉을것이다.

 

 

여기서 특수 알고리즘이란  바로 "플로이드 와샬" 알고리즘이다.

최단거리 경로 구하는 문제에서 거의 치트키급의 존재

 

플로이드 와샬 이란?

 

정점과 정점 으로 가는 모~~~든 케이스의 최단거리를 구해주는 알고리즘이다.

 

구현 방법은 다음과 같다.

 

1.int[][]  map을 생성한뒤,  모든 칸에 INF값(나올 수 있는 최댓값) 을 부여한다. (단, 자기 자신 i==j 일땐 0을 준다)

2. map을 그린다. (데이터 입력)  왕복케이스 까지 고려하면 map[i][j] 와 함께 map[j][i]도 입력한다.

 

3. 플로이드 알고리즘을 적용한다.

 

 

근데 플로이드 알고리즘 구현하면 끝인가?  NO

 

이건 직접 해보면안다.  플로이드 알고리즘으로 구한  s->a  경로와  s->b 경로를 더한값이

문제 예시에 있는 합승기믹을 적용한 값과 일치하지 않는 결과를 볼 수 있다.

 

여기서 합승 기믹을 어떻게 추가를 할까? 를 생각해야한다.

 

여기서 플로이드 와샬 알고리즘의 강점이 또 나타난다.

아까 말했듯이, 모든 정점과 모든 정점 사이에 최단거리를 구해준다.

 

즉,  합승을 마지막으로 하는 지점을 K 라고 한다면,

S -> K   +  K->A + K -> B 를 구하면 되는것이다!

 

 

단, 문제 예시 2번처럼 합승을 안하는게 오히려 더  낮은 최소비용을 가질수 있으니,

s->a +  s->b 역시도 비교를 해주자.

 

 

전체코드:

import java.util.*;
class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int max=1000001*n;
        
        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;
                    continue;
                }
                map[i][j]=max;
                
            }
        }
        
        int x, y, time =0;
        
        for(int i=0;i<fares.length;i++){
            x = fares[i][0]-1;
            y = fares[i][1]-1;
            time = fares[i][2];
            map[x][y]=time;
            map[y][x]=time;
        }
        
        
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<n;k++){
                    if(map[j][k]>map[j][i]+map[i][k]){
                        map[j][k]=map[j][i]+map[i][k];    
                    }
                }
            }
        }
        
        int total=Integer.MAX_VALUE;
        
        //합승 기믹 적용
        for(int i=0; i<n;i++){      
            total=Math.min(total,map[s-1][i]+map[i][a-1]+map[i][b-1]);            
        }
        
        //합승을 안했을때도 비교를 해주자
        total=Math.min(total,map[s-1][a-1]+map[s-1][b-1]);
        
        return total;
    }
    
}