[2] 합승 택시 요금

문제 추천 이유!!

최단거리 문제 필수 알고리즘 활용 => Floyd

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/72413

*작성가이드 입니다.

작성자가 먼저 문제를 풀어봅니다.
문제를 풀고나서 난이도를 설정합니다.
- 1 : 30분 이내로 손 쉽게 풀 수 있음
- 2 : 1시간 이내로 고민하면 풀 수 있음
- 3 : 1시간 이상 걸리거나 어려움
Coding test Basic template을 사용하여 이슈를 생성합니다.
- 제목은 : [난이도] 문제명으로 작성합니다.
- 내용은 : 문제 링크만 추가하세요
- 문제 사이트를 label로 추가해주세요. 기본값은 백준
문제 풀이는 이슈의 코멘트로 추가해주세요
- 풀이에 걸린 시간, 풀이 유형, 방식은 간단하게
- 문제를 풀고나서 스스로 풀이 또는 오답노트를 정리하는 느낌으로!!
다른 사람에게 채팅으로 직접 문제를 추천하세요.
- 디스코드 채널을 통해 다른 모임원에게 문제를 추천
- 해당 모임원은 문제를 풀고 코멘트를 통해 추가로 공유하기!!

아래는 comment 템플릿입니다.(복사해서 사용)

⏰ 소요 시간 : 
🗂️ 유형 :

🖌️ 문제 풀이
-

⏰ 소요 시간 : 20분 🗂️ 유형 : 최단거리문제

🖌️ 문제 풀이

중간 경유를 통해 최단 시간이 걸리는 경로를 찾는 문제!! => Floyd 활용

def floyd(arr, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # i->j 와 i->k->j 가는 지점 중 최소값을 저장
                arr[i][j] = min(arr[i][k] + arr[k][j], arr[i][j])

def solution(n, s, a, b, fares):
    answer = 0
    import sys

    s, a, b = s-1, a-1, b-1

    # 2차원 그래프 생성
    arr = [[sys.maxsize for _ in range(n)] for _ in range(n)]

    # 본인 노드에서 본인 노드 가는 거리 0 으로 초기화 
    for i in range(n):
        arr[i][i] = 0

    for u, v, f in fares:
        arr[u-1][v-1], arr[v-1][u-1] = f, f

    floyd(arr, n)

    answer = sys.maxsize
    # 중간지점 체크
    for k in range(n):
        answer = min(answer, arr[s][k] + arr[k][a] + arr[k][b])

    return answer

brickstudy / AlgorithmsGround

[2] 합승 택시 요금 #4

문제 추천 이유!!

문제 링크