✍ Kotlin을 사용한 PS 문제 풀이를 위한 알고리즘
소속 중인 A&I 동아리에서 코딩 역량을 강화하기 위해
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는Kotlin을 기반으로 작성하였습니다.
다익스트라 알고리즘이란?
다익스트라 알고리즘은 최단 경로를 구하는 알고리즘 중 하나로,
특정 노드에서 다른 노드까지의 최단 거리를 구할 때 사용합니다.
단, 노드와 노드 사이의 간선 가중치가 음수인 경우에는 사용할 수 없습니다.
또한 다익스트라 알고리즘은 DP적인 성질을 가지며,
동작 과정에서는 탐욕법이 사용됩니다.
동작 과정
- 출발 노드를 지정합니다.
- 최단 거리 테이블을 초기화합니다.
- 현재 노드 중 아직 방문하지 않았고, 가장 거리가 짧은 노드를 선택합니다.
- 해당 노드를 거쳐 다른 노드로 가는 최소 거리를 갱신합니다.
- 3번과 4번 과정을 반복합니다.
예를 들어, 다음과 같은 노드와 간선이 있다고 가정해 보겠습니다.
A에서 C 노드까지 가고 싶을 때, 어떤 경로가 가장 빠를까요?
여기서는 무조건 A에서 C로 바로 가는 것보다,
A에서 B를 거쳐 C로 가는 것이 더 유리하다고 생각할 수 있습니다.
이처럼 노드와 간선을 확인하여 가장 짧은 거리를 찾는 과정을다익스트라 알고리즘이라고 합니다.
그럼 조금 더 복잡한 예를 들어보겠습니다.
이때 1번 노드에서 다른 노드들까지의 최단 거리를 어떤 과정으로 구할 수 있을까요?
동작 과정을 통해 이해해 보겠습니다.
- 출발 노드를 지정합니다.
출발 노드는 1번입니다.
- 최단 거리 테이블을 초기화합니다.
1번부터 6번 노드까지의 거리 테이블을 모두 INF(무한대)로 초기화합니다.
- 현재 노드 중 아직 방문하지 않았고, 가장 거리가 짧은 노드를 선택합니다.
아직 방문 처리되지 않은 노드 중 가장 거리가 짧은 1번 노드를 선택하고,
해당 노드를 방문 처리한 뒤 거리를 0으로 설정합니다.
- 해당 노드를 거쳐 다른 노드로 가는 최소 거리를 갱신합니다.
이때 1번 노드에서 갈 수 있는 모든 노드의 가중치가 갱신됩니다.
- 3번과 4번을 반복합니다.
1번 노드 이후에는 가장 거리가 짧은 2번 노드를 방문하게 되고,
이때 인접한 3번과 6번 노드의 거리를 확인하여 갱신합니다.
다만 3번 노드는 이미 거리 5가 더 짧기 때문에 값이 바뀌지 않습니다.
그다음으로 3번 노드가 가장 짧은 거리이므로,
3번 노드를 방문 처리합니다.
3번 노드에 인접한 노드는 4번 노드입니다.
따라서 4번 노드의 가중치를 갱신해 줍니다.
이후 4번 노드가 최소 거리 노드가 되므로,
4번 노드를 방문한 뒤 인접한 노드의 최소 거리를 다시 갱신합니다.
이러한 과정을 통해 최단 거리를 구할 수 있습니다.
그런데 여기서 5번 노드는 방문하지 않은 것을 확인할 수 있습니다.
이는 다익스트라 알고리즘이 DP적인 특성과 탐욕법의 특징을 함께 가지기 때문입니다.
단계를 거치며 확정된 노드의 최단 거리는 이후에 다시 갱신되지 않습니다.
즉, 한 번 선택된 노드의 최소 거리는 더 이상 변경되지 않습니다.
또한 다익스트라 알고리즘은 최단 거리를 계산하는 데 사용되므로,
라우팅 분야에서도 활용됩니다.
라우터는 다른 라우터까지의 최단 거리를 계산하기 위해
라우팅 테이블의 링크 상태를 바탕으로
항상 더 짧은 경로로 갱신합니다.
📌 결론
다익스트라알고리즘은 특정 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘입니다.
단, 간선의 가중치가 음수인 경우에는 사용할 수 없습니다.
또한 라우터와 같은 네트워크 환경에서 자주 활용되며,
DP적인 성질과 탐욕법의 특징을 함께 가진다는 점도 알아두시면 좋습니다.
추가로 아주 짧게 말하면, 특히 어색했던 부분은 이런 것들이었습니다.
조금이 설명하고자 합니다→조금 설명하고자 합니다A에서 C의 노드로 도착하고 싶은데→A에서 C 노드까지 가고 싶은데1부터 6까지의 가장 최단 경로→1번 노드에서 각 노드까지의 최단 경로최신화되지 않습니다→갱신되지 않습니다단계에서 시작된 노드의 최소거리→한 번 선택된 노드의 최소 거리
