[파이썬] 백준 프로그래머스 : 합승 택시 요금 (Lv3)

[파이썬] 백준 프로그래머스 : 합승 택시 요금 (Lv3)

 

 

프로그래머스

---

풀이

0. 방향성 생각

다익스트라, 플로이드 워셜 둘 다 가능한데 플로이드 워셜 구현 안해봐서 다익스트라로 풀이

시간복잡도도 다익스트라가 나아서 효율성 점수도 있겠다 다익스트라로 풀이.

1. 입력

import heapq as hq

def solution(n,s,a,b,info):
    
    graph = {i: {} for i in range(1,n+1)}
    for n1,n2,cost in info:
        graph[n1][n2] = cost
        graph[n2][n1] = cost

graph에 간선정보 업데이트

 

2. 다익스트라 함수 정의

    def dijkstra(start):

        costs = {node: 1e9 for node in graph}
        costs[start] = 0

        q = []
        hq.heappush(q,[costs[start],start]) 

        while q:      
            cost,x = hq.heappop(q)

            if cost > costs[x]:
                continue

            for nx,ncost in graph[x].items():
                new_cost = cost + ncost
                if new_cost < costs[nx]:
                    costs[nx] = new_cost
                    hq.heappush(q,[new_cost,nx])
        return costs
        
        cost_info = {i: dijkstra(i) for i in range(1,n+1)}

다익스트라로 구한 노드 끼리 최단거리를 리턴한다.

이후 cost_info에 cost_info[시작][도착]으로 값 얻어내기

.

3. 출력

    answer = []
    answer.append(cost_info[s][a]+cost_info[s][b])
    for i in range(1,n+1):
        answer.append(cost_info[s][i]+cost_info[i][a]+cost_info[i][b])
    return min(answer)

따로 가는경우, 합승 후 거쳐가는 경우 중 최소값 반환

---

전체코드

import heapq as hq

def solution(n,s,a,b,info):
    
    graph = {i: {} for i in range(1,n+1)}
    for n1,n2,cost in info:
        graph[n1][n2] = cost
        graph[n2][n1] = cost
    
    def dijkstra(start):

        costs = {node: 1e9 for node in graph}
        costs[start] = 0

        q = []
        hq.heappush(q,[costs[start],start]) 

        while q:      
            cost,x = hq.heappop(q)

            if cost > costs[x]:
                continue

            for nx,ncost in graph[x].items():
                new_cost = cost + ncost
                if new_cost < costs[nx]:
                    costs[nx] = new_cost
                    hq.heappush(q,[new_cost,nx])
        return costs
    
    cost_info = {i: dijkstra(i) for i in range(1,n+1)}
    
    answer = []
    answer.append(cost_info[s][a]+cost_info[s][b])
    for i in range(1,n+1):
        answer.append(cost_info[s][i]+cost_info[i][a]+cost_info[i][b])
    return min(answer)

 

코멘트

    cost_info = {i: dijkstra(i) for i in (s,a,b)}
    
    answer = []
    answer.append(cost_info[s][a]+cost_info[s][b])
    for i in range(1,n+1):
        answer.append(cost_info[s][i]+cost_info[a][i]+cost_info[b][i])
    return min(answer)

s,a,b에서만 돌리고나서

cost_info[i][a]로 노드 탐색하니까 키 에러났는데

cost_info[i][a]나 cost_info[a][i]나 무방향이라 똑같아서 다익 3번돌리고 답 구해줌.

 

노드마다 다익스트라 써도 통과하긴 함