https://programmers.co.kr/learn/courses/30/lessons/72413
이 문제는 프로그래머스의 2021 KAKAO BLIND RECRUITMENT 문제집에 속해 있는 문제입니다.
문제에서는 출발지(S)와 각각의 목적지(A와 B)가 주어지고, 출발지에서 두 목적지를 방문하기까지의 최소 비용(=최단 거리)을 구하는 것이 문제의 목표입니다.
해당 문제는 그래프의 최단 거리 문제로 이용할 수 있는 알고리즘은 다익스트라 알고리즘과 플로이드 와샬 알고리즘이 있습니다.
저는 플로이드 와샬 풀이 법을 선택했고, 그래프 최단 거리 문제와 알고리즘이 익숙하지 않아서 따로 공부를 한 후 문제에 도전했습니다.
플로이드 와샬 알고리즘 공부하고 연습이 필요하신 분은 아래의 문제를 먼저 푸는 것도 좋을 거 같습니다😊
https://www.acmicpc.net/problem/11404
접근 방식
1. 플로이드 와샬 알고리즘을 이용해서 모든 정점에서 모든 정점으로의 최단 거리를 계산
2. 초기 answer에 각각의 목적지로 합승하지 않고 따로 갈 때의 비용을 저장
3. 1 ~ n의 지점 각각을 한 번씩 경우지로 지정하고 출발 지점(S)에서 경유지를 들려 각각의 목적지로 가는 비용과 현재의 answer값과 비교 후 최솟값을 answer에 저장
3번 단계에서 사용된 비교식
answer = min(answer, 비용[S -> (경유지)] + 비용[(경유지) -> A] + 비용[(경유지) -> B])
전체 코드
def calculate(n, dist):
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
def solution(n, s, a, b, fares):
answer = 0
dist = [ [ float('inf') ] * n for _ in range(n) ]
for i in range(n):
dist[i][i] = 0
for fare in fares:
c, d, f = fare
dist[c-1][d-1] = f
dist[d-1][c-1] = f
calculate(n, dist)
answer = dist[s-1][a-1] + dist[s-1][b-1]
for i in range(n):
answer = min(answer, dist[s-1][i-1]+dist[i-1][a-1]+dist[i-1][b-1])
return answer
읽어 주셔서 감사합니다 :)
잘못된 부분이 있다면 댓글로 편히 알려주세요😊
'PS > Python' 카테고리의 다른 글
[백준] 1916 - 최소비용 구하기 (파이썬, Python) (0) | 2021.09.28 |
---|---|
[백준] 21610 - 마법사 상어와 비바라기 (파이썬, Python) (0) | 2021.09.22 |
[백준] 1920 - 수 찾기 (파이썬, Python) (0) | 2021.09.19 |
[백준] 2644 - 촌수계산 (파이썬, Python) (0) | 2021.09.17 |
[백준] 15684 - 사다리 조작 (파이썬, Python) (0) | 2021.09.15 |