[알고리즘_카카오] 다익스트라 - 합승 택시 요금

[알고리즘_카카오] 다익스트라 - 합승 택시 요금

 

다익스트라 최단 경로 알고리즘

 

동작 과정

 

1. 출발 노드 설정
2. 최단 거리 테이블을 초기화
3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 3, 4번 과정 반복

 

처음에 이해가 안갔던 포인트가 방문한 노드는 그 노드까지의 최소 비용이 이미 결정된 상태라는 것이었다.

'다른 길로 둘러서 왔을 때 더 비용이 적으면 어떡하지?' 라는 생각을 했는데,

다시 생각해보면 새롭게 방문하게 되는 노드는 방문하지 않은 노드 중 가장 비용이 적은 노드라는 사실에서 그 명제가 참이 된다.

즉 다른 길로 돌아가는 것 자체의 첫발(첫 간선)부터 비용이 새롭게 방문하게 되는 노드로 가는 비용보다 더 크기 때문이다. (새로 가는 노드 비용이 최소이므로)

 

매 단계마다 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택해야한다.

1) 선형 탐색(순차 탐색)
2) heap을 이용한 탐색

 

순차 탐색을 이용한 풀이

다익스트라 처음 풀어봤는데, 정말 지옥에 떨어지는 줄 알았다...

시간이 오래 걸린 이유가 dijkstra 함수를 한 번 실행할 때마다 visited랑 cost를 초기화해줘야 하는데, solution 함수에서 visited와 cost를 선언한 후 dijkstra 함수에서 return 직전에 초기화 해줬더니 반여이 안되었다. 마치 call by value와 같은 느낌..

그래서 visited와 cost를 solution함수가 아니라 dijkstra 함수 초입부분에 선언하여 주었더니 해결됐다....

내 시간.... 쥬륵

아니 근데 파이썬은 int는 call by value로 list는 call by reference로 알고 있었는데 왜 배열이 초기화가 안되는거니..?

 

그 이유를 찾아보니 Python은 call by object-reference라고 한다...(뭐냐..)

함수 내에서 value = [0] * (n+1)로 초기화 하는 행위가 새로운 객체랑 binding하는 행위인데, 이 자체는 함수 밖에선 유효하지 않다고 한다. 하지만 element를 직접 조작하는, 예를들어 for문을 돌면서 visited[i] = 0 으로 직접 조작하였다면 참조하는 배열의 값이 바뀐다.

 

 

from collections import deque

def get_smallest_node(n,cost, visited):
    min_v = 1e9
    idx = 0 # 가장 비용이 적은 노드(인덱스)
    for k in range(1,n+1):
        if cost[k] < min_v and not visited[k]:
            min_v = cost[k]
            idx = k
    return idx


def dijkstra(start, end, n, graph):
    cost = [0] + [1e9]*(n)
    visited = [0] * (n+1)
    visited[start] = 1
    cost[start] = 0
    
    for j in graph[start]:
        cost[j[0]] = j[1]
    
    for i in range(1, n): # start 제외하고 n-1 다 비교
        now = get_smallest_node(n, cost, visited)# 가장 작은 비용인 값 구함
        visited[now] = 1
        # 다음 노드에 대해 새로운 경로가 기존 경로보다 싸면 비용 업데이트
        for next in graph[now]:
            new_cost = cost[now] + next[1]
            if new_cost < cost[next[0]]:
                cost[next[0]] = new_cost
    ans = cost[end]
    
    return ans 
        
def solution(n, s, a, b, fares):
    answer = 0
    # 간선 정보
    graph = [[] for _ in range(n+1)]
    minv = 1e9
    
    for fare in fares:
        graph[fare[0]].append((fare[1],fare[2]))
        graph[fare[1]].append((fare[0],fare[2]))
    for ii in range(1, n+1):
        # s 시작, ii 지점 경유, a, b에 각각 도착
        result = dijkstra(s, ii, n, graph) + dijkstra(ii, a, n, graph) + dijkstra(ii, b, n, graph)
        if result < minv:
            minv = result
    return minv

 

Heap을 사용한 풀이

 

from heapq import heappop, heappush

graph =[[]]
INF = 1e9

def dijkstra(start, end):
    global graph
    n = len(graph)
    c_table = [INF]*(n)
    c_table[start] = 0
    heap = [[0, start]]
    
    while heap:
        # 최소 cost 가진 노드가 pop
        cost_now, now = heappop(heap)
        # 다음 node들 확인. 기존 경로보다 새로운 경로가 더 비용이 적은 경우 찾음
        
        if cost_now > c_table[now]:
            continue
        
        for next in graph[now]:
            nx, ncost = next[0], next[1] 
            ncost += cost_now
            # 
            if ncost < c_table[nx]:
                c_table[nx] = ncost
                heappush(heap, [ncost, nx])
        
    return c_table[end]
        
def solution(n, s, a, b, fares):
    global graph
    answer = 0
    graph = [[] for _ in range(n+1)] # 간선 정보
    
    for fare in fares:
        src, dst, price = fare[0], fare[1], fare[2]
        graph[src].append([dst, price])
        graph[dst].append([src, price])
    
    cost = INF
    for mid in range(1, n+1):
        # s 시작, ii 지점 경유, a, b에 각각 도착
        cost = min(cost, dijkstra(s, mid) + dijkstra(mid, a) + dijkstra(mid, b))
            
    return cost