본문 바로가기

728x90

다익스트라2

[Algorithm] 다익스트라(Dijkstra) 알고리즘이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 그래프 문제에서 아주 빈번하게 사용되는 다익스트라라는 알고리즘에 대해서 알아보겠습니다. 바로 시작할게요! 다익스트라란? 🤔 나무 위키에는 다음과 같이 정의되어있습니다. "음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다." 쉽게 말하면 한 정점에서 다른 정점으로 이동할 때 가장 빠른 길을 찾아주는 알고리즘이에요. 그래프 설명 다음과 같은 그래프가 있다고 가정하겠습니다. 시작 정점은 1로 목표 정점을 4로 두었을 때 가장 가까운 거리는 몇일까요? 1 - 5 - 4 로 가는 경우가 3 + 1 = 4로 가장 가까운 길이겠죠? 이렇게 간단히 보이는 경로는 눈으로 쉽게 찾을 수 있지만 복잡한 경로일수록 찾기가 어려워질 것입니다. 이.. 2021. 5. 22.

[Swift] 프로그래머스 2018 Summer/Winter Coding 배달 Problem 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr Solution 해당 문제는 한 정점에서의 거리만 구하면 되기 때문에 다익스트라 알고리즘으로 풀어야 하는 문제다. (플로이드로 풀면 효율적이진 않지만 풀리긴 풀린다...) 다익스트라 풀이 1.모든 거리를 저장할 이차원 배열을 만들어줌. (allDistances 변수를 참고해주세요!) 2.다익스트라로 시작하는 정점에서 가장 가까운 거리를 찾아줌. (dijkstra 함수를 참고해주세요!) 4.1과 연결된 정점 중 주어진 시간 .. 2021. 5. 21.

이전 1 다음

728x90

티스토리툴바