23.03.28 파이썬 코딩 퀴즈#204 합승 택시 요금(프로그래머스 스쿨)

이번 문제는 합승 택시 요금이다.

전달받은 fares 를 기준으로 시작점 S, 그리고 두사람의 목적지 A,B 가 정해질 때, 최소 택시비를 구하는 문제이다.

위 그림을 기준으로 S -> A, S->B 의 최소 금액을 구해야 한다.

먼저 S -> A , S-> B 최단 거리로 가게 되면 각 50원 과 66원이 든다

하지만 두 사람이 합승하여 4(S) -> 1-> 5 로 이동하면 비용은 34원이다.

그 다음 A가 5번 지점에서 내려 6번으로 이동하면 추가로 2원이 든다

B 는 혼자서 5->3->2 로 이동하게 되면 46원이다. 이 때 총 요금은 34 + 2 + 46 = 82 원 이다.

딱히 설명에서 어려운 부분은 없다.

배열의 크기도 의미가 없다. 배열에서 챙겨야 할 부분은 c,d,f 값 이며, c->d, d->c 모두 같은 값 f 를 가진다

입출력 예제 1은 위 그림 설명과 같다.

입출력 예제3을 살펴보면

전달받은 fares 에는 1번으로 가는 도로가 존재하지 않는다. 따라서 위 그림처럼 1번은 외딴섬으로 표현된다.

6번을 기준으로 동서남북으로 연결되어 있으며, S 에서 A, B로 가는 최소 요금합계는

4(S) - > 6(B) -> 5(A) 로 가는 18원 이다.

 

이 문제의 핵심은 합승이다. 즉 특정 지역으로 이동 하여서 각기 다른 최소금액으로 이동시의 금액도 확인을 해야 한다.

따라서.

1. 시작점 S 로 부터 각 A, B 지점으로 가는 금액 확인

2. S에서 이동 가능한 한 지점으로 이동 후 A,B로 가는 금액 확인

3. 그 다음 지점에서 A,B 로 이동하는 금액 확인 (최소값 갱신)

위 과정을 거쳐 S부터 목적지까지의 최소 요금의 합을 확인해야 한다.

문제를 다 풀고 알았지만, 비전공자에겐 그 어떤 알고리즘도 어려울 뿐이다.

그동안 갈고 닦은 기본기로 승부해보았다. ( 정작 코드 짜는데 2일이나 걸렸다)

먼저 전달받은 fares 에서 각 지점에 연결된 도로와 비용을 roads 에 dict 로 저장해 두었다.

그리고 이제 costs 라는 2차원 배열을 만들어야 한다. 

위 코드에도 주석을 달아 놓았지만, costs[i][j] 는 i 에서 j 로 가는 값을 의미한다.

나 처럼 0번 마을까지 생각한 경우라면 당연히 n+1 까지 범위를 지정해서 만들어야 한다.

아니라면, 각 index 값에 -1을 해주어서 1번 마을이 index 0 이 되게 만들어야 한다.

그리고 제일 중요한건 costs[i][i] 는 0으로 해주어야 한다. 그렇지 않으면 가장 가까운 마을을 왕복한 값을 얻게된다...

이제 본격적으로 반복문을 통해 각 기준마을(i) 에서 그 다음 마을(j)로 가는 최소요금을 구해야 한다.

min() 함수를 사용하게 되면, history 도 필요하고 여러가지 설정해 주어야할 변수들이 많다.

따라서 위 코드에서는 현재 값보다 새로운 길로 돌아온 값이 적을때에만 값을 갱신해 주고, 그 갱신된 값을 기준으로 j마을을 기준으로 값들을 다시 확인해 주었다.

한 마을(i)를 기준으로 탐색이 끝난 다음에는 costs[i][a] (i 에서 a로 가는 비용) + costs[i][b] (i에서 b로 가는 비용) + costs[i][s] (i에서 s로 가는 비용) 세가지를 합상하여 최소값을 answer로 갱신해 주었다.

이때 중요한 합승 비용이 바로 costs[i][s] 이다. 왕복 도로이기 때문에 costs[i][s] 는 i에서 s로 가는 비용이자, s에서 i로 가는 비용이 된다.