다익스트라2 [Algorithm] 다익스트라 알고리즘 인접리스트로 풀기 인접 리스트로 풀기 다익스트라 문제의 경우 인접 리스트로 푸는 경우가 많다고 한다. 왜냐하면 힙을 이용해 시간 복잡도를 줄일 수 있기 때문이다. 여기서 힙이란 스택과 대비되는 자료구조 중의 하나로 개발자가 직접 할당해서 사용하는 메모리 부분이다. 그렇다면 아래 문제를 한번 인접리스트로 풀이해 보겠다. 문제 무방향 그래프의 한 정점(vertex)에서 다른 정점까지의 최단 거리를 리턴해야 합니다. 입력 인자 1: num number 타입의 자연수 그래프에 존재하는 정점의 개수 정점은 1부터 num까지 존재 인자 2: edges 배열(간선에 대한 정보)을 요소로 갖는 배열 edges [i]는 number 타입을 요소로 갖는 배열 edges [i]. length는 3 edges [i]의 요소는 차례대로 정점, .. 2022. 3. 25. [Algorithm] 다익스트라 알고리즘 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다. 다른 최단거리 알고리즘으로는 벨만 포드와 플로이드 와샬 알고리즘이 있는데 이는 다른 포스팅에서 다루기로 하겠다. 다익스트라 알고리즘의 핵심은 1. 노드간의 거리를 나타내는 매트릭스와 방문 기록 배열을 만든다. 2. 매트릭스에 노드간 거리를 넣는다. 3. 출발 노드에서 가장 작은 비용으로 갈 수 있는 노드를 구한다. 4. 최소거리 노드로 이동하며 방문 기록을 True로 변경한다. 5. 최소거리 노드까지 이동하는 거리를 더한 참조 배열을 만들고 출발 노드와의 거리와 비교해 더 작은 값을 대입한다. 6. 과정을 반복한다. 아래 예제를 풀어보자. https://www.acmicpc.net/problem.. 2022. 3. 24. 이전 1 다음
