[프로그래머스]합승택시요금_Java

--문제--

https://programmers.co.kr/learn/courses/30/lessons/72413?language=java 

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

--문제풀이--

문제에 대하여 그래프 문제로 방향성이 없는 연결 그래프에서 최단 경로를 구하는 문제였다.

그래서 생각해본 결과 플로이드와 다익스트라로 풀이를 해보는 것으로 결정하여 문제를 풀이를 진행했습니다.

플로이드 하면서 가장 중요한 점은

경 출 도

경유지 출발지 도착지 가 가장 중요하고

다익스트라에선 중요한 건

한지점 A기준으로만 최단거리를 구하는 것이라는 것을 인지하여 코드를 구현하는 것입니다.

-- 코드--

플로이드

package Level3;

public class 합승택시요금_플로이드 {
	public static void main(String[] args) {
		int[][] temp= {{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}};
		System.out.println(solution(6,4,6,2,temp));
	}
	

	    public static int solution(int n, int s, int a, int b, int[][] fares) {
	        int answer = Integer.MAX_VALUE;
	        int[][] map=new int[n+1][n+1];
	        for(int i=1;i<=n;i++){
	            for(int j=1;j<=n;j++){
	                map[i][j]=20000001;
	            }
	            map[i][i]=0;
	        }
	        for(int i=0;i<fares.length;i++){
	            map[fares[i][0]][fares[i][1]]=fares[i][2];
	            map[fares[i][1]][fares[i][0]]=fares[i][2];
	        }
	        //플로이드 와샬의 가장 중요한 경 출 도
	        for(int k=1;k<=n;k++){//경유지
	            for(int i=1;i<=n;i++){//출발지
	                for(int j=1;j<=n;j++){//도착지
	                    if(map[i][j]>map[i][k]+map[k][j]){
	                        map[i][j]=map[i][k]+map[k][j];
	                    }
	                }
	            }
	        }
	        for(int i=1;i<=n;i++){
	            answer=Math.min(answer,map[s][i]+map[i][a]+map[i][b]);
	        }
	        
	        return answer;
	}

}

 다익스트라 

package Level3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

public class 합승택시요금_다익스트라버전 {
	public static void main(String[] args) {
		int[][] temp= {{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}};
		System.out.println(solution(6,4,6,2,temp));
	}
	static class node implements Comparable<node>{
		int to,weight;
		public node(int to, int weight) {
			super();
			this.to = to;
			this.weight = weight;
		}
		@Override
		public int compareTo(node o) {
			return this.weight-o.weight;
		}	
	}
	static List<ArrayList<node>> list =new ArrayList<>();
	public static int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = Integer.MAX_VALUE;
        for(int i=0;i<=n;i++) {
        	list.add(new ArrayList<>());
        }
        for(int i=0;i<fares.length;i++) {
        	list.get(fares[i][0]).add(new node(fares[i][1],fares[i][2]));
        	list.get(fares[i][1]).add(new node(fares[i][0],fares[i][2]));
        }
        
        int[] startA=new int[n+1];
        int[] startB=new int[n+1];
        int[] start=new int[n+1];
        Arrays.fill(startA, 20000001);
        Arrays.fill(startB, 20000001);
        Arrays.fill(start,20000001);
        startA=Dijkstra(a,startA);
        startB=Dijkstra(b,startB);
        start=Dijkstra(s,start);
        for(int i=1;i<=n;i++){
        	answer=Math.min(answer, startA[i]+startB[i]+start[i]);
        }
        
        
        return answer;
}
	private static int[] Dijkstra(int start,int[] costs) {
		PriorityQueue<node> pq=new PriorityQueue<>();
		for(node cur:list.get(start)) {
			costs[cur.to]=cur.weight;
		}
		costs[start]=0;
		for(node temp:list.get(start))pq.add(temp);
		while(!pq.isEmpty()) {
			node curnode=pq.poll();
			if(costs[curnode.to]<curnode.weight)continue;
			for(node next:list.get(curnode.to)) {
				if(costs[next.to]>curnode.weight+next.weight) {
					costs[next.to]=curnode.weight+next.weight;
					pq.add(new node(next.to,curnode.weight+next.weight));
				}
			}
		}
		
		
		return costs;
		
	}

}