[프로그래머스] 합승 택시 요금(72413)

문제

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

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

 

문제 접근

1번 s -> a -> b

2번 s -> b -> a

3번

      s -> a

      s -> b

 

위와 같은 형식으로 접근했으나, 문제의 예제와 같이 중간에서 갈라지는 케이스를 생각하지 못했다.(문제를 잘못읽음)

"문제풀이 1" 같이 풀었다.

 

방법이 떠오르지 않아, 블로그를 찾아보았다.

참고 블로그
https://moonsbeen.tistory.com/51

 

플로이드-와샬 알고리즘 이라는 용어가 나왔다.

간략하게 설명하면,  알고리즘은 두 꼭짓점 간의 추정 최단 경로를 최적이 될 때까지 점진적으로 개선시켜서 최단경로를 찾는 방식이다.

 

풀이 방식은

현재 node[i][j]로 가는 비용보다 더 작은 값으로 node[i][j]로 갈 수 있는 경로를 발견한다면 그 값으로 갱신해 주면 된다.

즉, node[i][j]보다 node[i][k] + node[k][j] (k를 경유해서 가는 방법)이 더 작은 값이라면 갱신해준다.

이런 방법으로 모든 노드에서 모든 노드로 가는 최단 경로를 알 수 있다. 시간 복잡도는 O(n^3)으로 다소 오래걸리는 편이다.

"문제풀이 2" 같이 풀었다.

 

문제 풀이 코드

#문제풀이 1

package kakaoBlind_2021;

import java.util.LinkedList;
import java.util.Queue;

class P{
	int x;
	int y;
	int pay;
	boolean[][] b;
	
	public P(int x, int y, int pay, boolean[][] b) {
		this.x=x;
		this.y=y;
		this.pay=pay;
		this.b=b;
	}
}

public class S_72413 {

	// 지점갯수 n
	// s : 출발지점 / a : 도착지점 / b : 도착지점
//	fares[c, d, f] : c와 d의 f요금 ( fares[d, c, f] 와 같음 )
	
	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}};	
		System.out.println(solution(n, s, a, b, fares));
	}
	public static int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        
        int[][] map = new int[n+1][n+1];
        
        for(int i=0;i<fares.length;i++) {
        	int x = fares[i][0];
        	int y = fares[i][1];
        	int val = fares[i][2];
        	map[x][y] = val;
        	map[y][x] = val;
        }
        
//        print(map);
        
//      case 1 : s -> a -> b
//      case 2 : s -> b -> a
//      case 3 :
//      	s -> a
//      	s -> b
        answer = bfs(map, s, a, b);
        
        return answer;
    }
	public static int bfs(int[][] map, int s, int a, int b) {
		
		// s -> a
		System.out.println("*********** s -> a *********** ");
		int minPay_SToA = findMinPay(map,s,a);
		System.out.println("-------------- minPay_SToA : "+minPay_SToA+" ----------------");
		// a -> b
		System.out.println();
		System.out.println("*********** a -> b *********** ");
		int minPay_AToB = findMinPay(map,a,b);
		System.out.println("-------------- minPay_AToB : "+minPay_AToB+" ----------------");
		// s -> b
		System.out.println();
		System.out.println("*********** s -> b *********** ");
		int minPay_SToB = findMinPay(map,s,b);
		System.out.println("-------------- minPay_SToB : "+minPay_SToB+" ----------------");

		// b -> a
		System.out.println();
		System.out.println("*********** b -> a *********** ");
		int minPay_BToA = findMinPay(map,b,a);
		System.out.println("-------------- minPay_BToA : "+minPay_BToA+" ----------------");
		
		int StoAtoB = minPay_SToA+minPay_AToB;
		int StoBtoA = minPay_SToB+minPay_BToA;
		int StoBAndStoA = minPay_SToA+minPay_SToB;
		
		return Math.min(Math.min(StoAtoB, StoBtoA), StoBAndStoA);
		
	}
	public static int findMinPay(int[][] map, int start, int end) {
		Queue<P> q = new LinkedList<P>();
		q.add(new P(0,start,0,new boolean[map.length][map[0].length]));
		int minPay = Integer.MAX_VALUE;
		while(!q.isEmpty()) {
			P p = q.poll();
			int fx = p.x;
			int fy = p.y;
			int pay = p.pay;
//			boolean b[][] = p.b.clone();
			boolean b[][] = copyBooleanMap(p.b);
			
			System.out.println(fx+" "+fy+" "+pay);
			if(fy==end) {
				minPay = Math.min(minPay, pay);
				System.out.println("--------> minPay : "+minPay);
			}else {
				for(int i=1;i<map[0].length;i++) {
					if(map[fy][i]!=0 && fx!=i && fy!=i && !b[fy][i]) {
						System.out.println(">> "+fy+" "+i+" <<");
						b[fy][i] = true;
						q.add(new P(fy, i, pay+map[fy][i],b));
					}
				}
			}
		}
		return minPay;
	}
	public static boolean[][] copyBooleanMap(boolean[][] b){
		boolean[][] newBoolean = new boolean[b.length][b[0].length];
		for(int i=1;i<b.length;i++) {
			for(int j=1;j<b[0].length;j++) {
				newBoolean[i][j]=b[i][j];
			}
		}
		return newBoolean;
	}
	public static void print(int[][] map) {
		for(int i=1;i<map.length;i++) {
			for(int j=1;j<map[0].length;j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
	}
}

 

#문제풀이 2

package kakaoBlind_2021;


public class S_72413_1 {

	// 지점갯수 n
	// s : 출발지점 / a : 도착지점 / b : 도착지점
//	fares[c, d, f] : c와 d의 f요금 ( fares[d, c, f] 와 같음 )
	
	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}};	
		System.out.println(solution(n, s, a, b, fares));
	}
	public static int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        
        int[][] map = new int[n+1][n+1];
        // map의 n, m을 모두 max 페이로 셋팅(n==m 일 경우는 0으로 셋팅)
        for(int i=1;i<n+1;i++) {
        	for(int j=1;j<n+1;j++) {
        		map[i][j] = 20000001;	// 200 * 100,000 + 1
        	}
        	map[i][i] = 0;
        }
        
        // 경로 있는 부분 셋팅
        for(int i=0;i<fares.length;i++) {
        	int x = fares[i][0];
        	int y = fares[i][1];
        	int val = fares[i][2];
        	map[x][y] = val;
        	map[y][x] = val;
        }
        
        // 플로이드-와샬 알고리즘
        // 현재 node[i][j]로 가는 비용보다 더 작은 값으로 node[i][j]로 갈 수 있는 경로를 발견한다면 그 값으로 갱신
        for(int k=1;k<n+1;k++) {
        	for(int i=1;i<n+1;i++) {
        		for(int j=1;j<n+1;j++) {
                	if(map[i][j]>map[i][k]+map[k][j]) {
                		map[i][j] = map[i][k]+map[k][j];
                	}
                }	
            }	
        }
        
        int minValue = Integer.MAX_VALUE;
        for(int i=1;i<n+1;i++) {
        	// "s부터 i까지 최단 경로 + i부터 a까지 최단 경로 + i부터 b까지 최단 경로" 의 최단 경로
        	minValue = Math.min(minValue, map[s][i]+map[i][a]+map[i][b]);
        }
        answer = minValue;
        return answer;
    }
}