다익스트라2 [프로그래머스] 합승 택시 요금 문제 밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다. 위 예시 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이동 가능한 택시노선과 예상요금을 보여주고 있습니다. 그림에서 A와 B 두 사람은 출발지점인 4번 지점에서 출발해서 택시를 타고 귀가하려고 합니다. A의 집은 6번 지점에 있으며 B의 집.. 2022. 6. 8. [알고리즘] 다익스트라 알고리즘 다익스트라 알고리즘(데이크스트라) 그래프에서 어떠한 점(A)에서 어떠한 점(B)으로 가는 최단 거리를 구할 때 사용하는 알고리즘입니다. 핵심 1. 다익스트라는 BFS의 확장 같은 느낌.(현재 점에서 연결되어 있는 모든 점 검사,,, 그러나 이미 거리가 확정된 곳은 제외) 2.거리 배열을 하나 만들어서 각 점을 할당한다. 각 배열이 의미하는 바는 시작지점에서 해당 지점까지 얼마나 걸리는지 기록. 3.가중치에 음수가 있다면 알고리즘 성립안됨!! (1) S1에서 시작하여, 배열 안 S2,S3 값을 1,5로 초기화합니다. (2) 현재 위치에서 가까운 S2로 갑니다. (3) S2에서 S3로 가는데 3의 비용이 듭니다. 현재 누적된 S2의 비용(1) + S3로 가는 비용(2) VS 기존에 있는 S3의 값(S1->S.. 2022. 2. 25. 이전 1 다음 반응형
