programmers.co.kr/learn/courses/30/lessons/72413
코딩테스트 연습 - 합승 택시 요금
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
작년에 봤었던 카카오 블라인드 2021문제였다.
작년에 3-7번 문제중 가장 만만한 문제였던 것으로 기억하는데
최단거리 알고리즘을 알고있어야 풀 수 있는 문제였다.
하지만 작년에 시간초과로 인해 70%점수만 받았다.
이유를 알고보니 모든 정점에서 dijkstra를 사용한 것이 화근이었다.
문제 풀이과정은
S지점으로 부터 dijkstra를 돌려서 각 정점마다 최단거리를 구한다.
그리고
A, B 각 지점에서 dijkstra를 돌려서 최단거리를 구해놓는다.
글쓴이는 작년에 모든 정점 1-n까지 모든 dijkstra를 돌렸는데 이러면 시간초과난다..
시간 복잡도가 200log(200) * 200 이라고 생각했지만 생각 이상으로 시간초과 많이 들었나보다..
(혹시 틀렸으면 말해주세요.. 전 아직도 왜 이게 시간초과인지 모르겠습니다.)
**수정**
시간초과인 이유 - 간선이 많음 다익스트라 생각해보면 모든 간선 다보면서 best first search하는거라
이래도 간선 많아지면 시간초과남 그래서 플로이드-와샬로 푸는걸 추천
여기서부터는 간단하다.
모든 I지점(1-N)까지 보는데 만약 S, A, B 모두 I지점까지 갈 수 있는 경로가 있다면
S,A,B 에서 I지점까지의 최단거리를 전부 더해서 최소인 정답만 구해주면 된다.
코드
'Algorithm' 카테고리의 다른 글
| 백준 - 17831번(머기업 승범이네) / C++ (0) | 2021.03.10 |
|---|---|
| 프로그래머스 - 매출 하락 최소화 / C++ (2) | 2021.03.08 |
| 프로그래머스 - 순위 검색 / C++ (0) | 2021.03.04 |
| 프로그래머스 - 신규 아이디 추천 / C++ (0) | 2021.03.03 |
| 백준 - 2146번(다리 만들기) / C++ (0) | 2021.02.27 |