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

[프로그래머스] 합승 택시 요금(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 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 q = new LinkedList(); 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> "+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

#문제풀이 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;imap[i][k]+map[k][j]) { map[i][j] = map[i][k]+map[k][j]; } } } } int minValue = Integer.MAX_VALUE; for(int i=1;i

from http://bang-log.tistory.com/86 by ccl(A) rewrite - 2021-10-24 18:27:14