2021. 2. 15. 15:46ㆍ코딩테스트
programmers.co.kr/learn/courses/30/lessons/72413?language=python3
코딩테스트 연습 - 합승 택시 요금
6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4
programmers.co.kr
def solution(n, s, a, b, fares):
answer = n*1000001
d = [[n*100001]*n for _ in range(n)]
for k in range(n):
d[k][k] = 0
for fare in fares:
x, y, f = fare
d[x-1][y-1] = f
d[y-1][x-1] = f
for k in range(n):
for i in range(n):
for j in range(n):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
for k in range(n):
answer = min(answer, d[s-1][k] + d[k][a-1] + d[k][b-1])
return answer
Floyd-Warshal 알고리즘을 사용해서 풀었습니다.
모든 정점에서 모든 정점으로의 최단거리를 구하고
출발점 s에서 모든 정점을 거쳐 a, b로 가는 비용을 계산하고 최소값을 구합니다.
공식해설에는 다익스트라 알고리즘으로도 풀 수 있다고 나와있습니다.
tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/
2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설
지난 2020년 9월 12일 토요일 오후 2시부터 7시까지 5시간 동안 2021 카카오 신입 개발자 공채 1차 코딩 테스트가 진행되었습니다. 테스트에는 총 7개의 문제가 출제되었으며, 개발 언어는 C++, Java, Jav
tech.kakao.com
프로그래머스 2021 KAKAO BLIND RECRUITMENT 메뉴 리뉴얼 파이썬 python 카카오 신입공채 온라인 코딩 테스트
'코딩테스트' 카테고리의 다른 글
| 2021 KAKAO BLIND : 카드 짝 맞추기 (프로그래머스) (1) | 2021.02.23 |
|---|---|
| 2020 카카오 인턴십: 경주로 건설 (프로그래머스) (0) | 2021.02.15 |
| 2021 KAKAO BLIND : 메뉴 리뉴얼 (프로그래머스) (0) | 2021.02.05 |