Q4. 합승 택시 요금

1. 문제유형

Programmers 링크 공유
https://programmers.co.kr/learn/courses/30/lessons/72413

1-1 입출력 예시

2. 소스코드

INF = int(1e9)
node = [[]]

import heapq

def makeNodes(fares):
    global node

    for src,dst,cost in fares:
        node[src].append([dst,cost])
        node[dst].append([src,cost])
    
    
def dijkstra(src,dst):
    global node
    localCost = [INF] * (len(node))
    localCost[src] = 0
    
    route = [[0,src]]
    
    while route:
        curCost, curRoute = heapq.heappop(route)
        
        if curCost > localCost[curRoute]:
            continue
        
        for nextRoute,nextCost in node[curRoute]:
            nextCost += curCost
            
            if nextCost < localCost[nextRoute]:
                localCost[nextRoute] = nextCost
                heapq.heappush(route, [nextCost,nextRoute])
    
    return localCost[dst]


def solution(n, s, a, b, fares):
    global node
    answer = 0
    node = [[] for _ in range(n+1)]

    makeNodes(fares)
    
    answer = dijkstra(s,a) + dijkstra(s,b)
    
    for i in range(1,n+1):
        if i != s:
            answer = min(answer,dijkstra(s,i)+dijkstra(i,a)+dijkstra(i,b))
    return answer

3. 문제 풀이

본 문제의 핵심 원리는 다익스트라(dijkstra) 알고리즘이다.

다익스트라 알고리즘: 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘
특정 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.

본 문제에서 다익스트라를 어떻게 활용하여 풀었는지 그 과정을 살펴보도록 하겠다.

3-1 노드 생성

위 문제는 쌍방향 이동이 가능하다는 조건을 가지고 있다.

쌍방향 이동: A에서 B 이동 가능, B에서 A 이동 가능
단방향 이동: A에서 B 이동 가능, B에서 A 이동 불가

그럼 코드를 통해 알아보겠다.

node = [[]]

def makeNodes(fares):
	for src, dst, cost in fares:	// 쌍방향 노드 생성
    		node[src].append([dst,cost])
            node[dst].append([src,cost])

def main(){
	global node
    	node = [[] for_ in range(n+1)]	// node 초기화

위 코드를 통해 node라는 이중 배열안에 쌍방향 이동이 가능하도록 작성하였다.
이를 통해 src에서 dst로 갈 때, cost만큼 소비되고 / dst에서 src로 갈 때도 cost만큼 소비된다.

3-2 다익스트라 알고리즘 구현

INF = int(1e9) // 임의의 MAX값 세팅

import heapq

def dijkstra(src,dst):
	global node
    	localCost = [INF] * len(node)
    	localCost[src] = 0
    
    	route = [[0,src]]
        
        while route:
        	curCost,curRoute = heapq.heappop(route)
            
            if curCost > localCost[curRoute]:
            	continue
               
            for nextRoute,nextCost in node[curRoute]:
            	nextCost += curCost
                
                if nextCost < localCost[curRoute]:
                	localCost[curRoute] = nextCost
                    heapq.heappush(route,[nextCost,nextRoute])
                    
        return localCost[dst]

다익스트라 알고리즘은 모든 노드를 while문을 통해 탐색하는 방식(=bfs)으로 진행되기 때문에 데이터 범위가 클 경우, Time Out의 문제가 발생할 수 있다.

그러므로 조금이라도 그 시간을 줄이기 위해 heapq을 통해 탐색을 진행한다.

heapq: 이진트리 기반의 최소 힙 자료구조를 제공한다.

• heappop을 할 경우, 위 알고리즘을 통해 가장 최소 값을 반환한다.

1. localCost: 각 노드의 cost 값(src ~ 해당 노드로 오기까지의 cost 합)

• 초기에는 src(=시작점)을 제외하고 모두 무한대 값(=INF)로 초기화시킨다.
• while문이 종료된 후, localCost 배열에는 src ~ 해당 노드들까지 가는데 걸리는 cost의 최소 합들이 저장되게 된다.

2. heapq를 통한 초기화:
   [0,src]로 초기화하며 while문에서 heappop을 할 때마다 curCost가 제일 작은 요소가 반환된다.

3. if curCost > localCost[curRoute]:
   현재 route에서 반환된 값(=curCost)이 현재 저장되어 있는 값(=localCost[curRoute])보다 클 경우, 우리는 최소값을 구해야 하기 때문에 더이상 하위를 진행할 필요가 없으므로 continue 처리

4. heapq에 저장: 위의 1,2,3과정을 모두 만족하는 값에 대해 연결되어 있는 다음 노드를 확인하고 조건에 맞을 경우, heapq에 저장하는 과정을 반복한다.

5. return localCost[dst]:
   while문이 종료되면 localCost에는 각 idx로 가기까지의 최소값이 저장된다. 그러므로 src ~ dst까지의 최솟값은 localCost[dst]에 저장되어 있으므로 이를 반환한다.

3-3 메인함수

def solution(n, s, a, b, fares):
			.
            		.
                    	.
    answer = dijkstra(s,a) + dijkstra(s,b)
    
    for i in range(1,n+1):
        if i != s:
            answer = min(answer,dijkstra(s,i)+dijkstra(i,a)+dijkstra(i,b))
    return answer

마지막으로 우리는 두 가지 경우의 수를 비교해야 한다.

1. a와 b가 처음부터 끝까지 따로 가는 경우

• answer = dijkstra(s,a) + dijkstra(s,b)

2. a와 b가 i라는 지점까지 함께 동승 + i ~ 목적지까지 따로 가는 경우

• answer = dijkstra(s,i)+dijkstra(i,a)+dijkstra(i,b)

두가지 경우에 대한 값을 모두 확인해야 하고 최종적으로 둘 중 최소값을 answer에 저장하는 것이다.

위의 코드는 그 과정을 작성한 것이고 결과적으로 우리는 answer을 도출하게 된다.

4. 마무리

오늘은 다익스트라 알고리즘을 활용하는 문제를 풀어보았다.
예전 삼성 공채 코딩테스트, ACM-ICPC 대회 준비를 할 때도 DFS, BFS를 기반으로 하는 문제가 많이 나왔었다. 그만큼 사람을 고민하게 만들고 중요하기 때문이라고 생각되지만 풀 때마다 어려운건 마찬가지다...ㅎ
꾸준히 문제를 풀어가며 익히는 방법밖에는 없을 것 같다!

전체 소스 git 링크
https://github.com/cho876/Algorithm/blob/master/Problem/Kakao/2021_kakao_blind_recruitment_q4.py