얼마 전?은 아니고 몇달 전 면접에서 길 찾기 알고리즘에 대한 질문을 받았다.
당연히 공부했던 것들이고 알고 있다고 생각했는데 막상 대답하려니까 알고리즘 이름도 기억이 안 나고 특징도 가물가물하니... ~.~
그런 의미에서 길 찾기 알고리즘 하나하나 되짚어보기 시간
오늘 주제는 다익스트라 알고리즘
다익스트라(Dijkstra) 알고리즘
정의와 특징
- 최단 경로를 찾기 위해 사용되는 알고리즘
- 특정 출발점부터 다른 정점까지의 최단 경로를 구하는 문제를 해결할 때 사용
- 모든 간선의 가중치가 양수일 때만 사용 가능
- 각 정점까지의 최단 거리를 점진적으로 계산하는 그리디 알고리즘의 한 형태
활용 분야
- 활용분야
- 길 찾기 애플리케이션 : 출발지와 목적지 사이 최단 경로
- 네트워크 라우팅 : 패킷 스위칭 네트워크에서 데이터 패킷의 최적 경로를 결정할 때
- 자원 할당 : 자원을 효율적으로 할당하기 위해 사용
- DNA 시퀀싱 : 유전자 간의 거리를 계산
동작 단계
- 출발 노드와 도착 노드를 설정
- 최단 거리 테이블을 초기화
- 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택하여 방문 처리
- 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용을 계산해 최단 거리 테이블을 업데이트
- 3 ~ 4 과정을 반복
시간 복잡도
- 기본 : O(V^2)
- 우선순위 큐를 이용해 구현 : O(E * logv)
예제
문제
N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.
모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
출력
첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
문제
- 예전에 자바로 풀었던 적이 있는 문제..였으나 기억 상실 이슈
- 문제의 포인트는 목적지에 갔다가 돌아온다는 것이다.
- A -> X -> A 경로의 최단 거리를 구하는 것
- 정해진 출발지로부터 최단 거리를 구하는 다익스트라 알고리즘을 사용하면 X -> A 의 최단 거리는 쉽게 구할 수 있다.
- 그럼 A -> X 는 어떻게 구할 것인가?!
- 모든 정점을 돌며 다익스트라 알고리즘을 수행하여 X까지의 최단 거리를 구할 수도 있지만 더 빠른 방법은 없을까!!!
해결
- 여기서 약간의 생각의 전환이 필요하다! 그래프 간선을 뒤집어보자
- 간선 방향이 뒤집힌 그래프에서 X -> A 경로의 최단 거리를 구해보면 결국 이게 A -> X 경로의 최단 거리가 됨을 알 수 있다.
- 헷갈릴 땐 그래프를 직접 그려보면 됨
코드
class Node
{
public int idx;
public int cost;
public Node(int idx, int cost)
{
this.idx = idx;
this.cost = cost;
}
}
static void Main(string[] args)
{
string[] str = Console.ReadLine().Split(" ");
int N = int.Parse(str[0]);
int M = int.Parse(str[1]);
int X = int.Parse(str[2]);
List<List<Node>> graph = new List<List<Node>>();
List<List<Node>> reverseGraph = new List<List<Node>>();
for (int i = 0; i < N + 1; i++)
{
graph.Add(new List<Node>());
reverseGraph.Add(new List<Node>());
}
for (int i = 0; i < M; i++)
{
string[] edges = Console.ReadLine().Split(" ");
int start = int.Parse(edges[0]);
int end = int.Parse(edges[1]);
int cost = int.Parse(edges[2]);
graph[start].Add(new Node(end, cost));
reverseGraph[end].Add(new Node(start, cost));
}
int[] dist = new int[N + 1];
int[] reverseDist = new int[N + 1];
for (int i = 0; i < N + 1; i++)
{
dist[i] = int.MaxValue;
reverseDist[i] = int.MaxValue;
}
Dijkstra(N, X, dist, graph);
Dijkstra(N, X, reverseDist, reverseGraph);
int result = -1;
for (int i = 1; i < N + 1; i++)
result = Math.Max(result, dist[i] + reverseDist[i]);
Console.WriteLine(result);
}
static void Dijkstra(int N, int start, int[] dist, List<List<Node>> graph)
{
bool[] visited = new bool[N + 1];
dist[start] = 0;
for (int i = 0; i < N; i++)
{
int nodeIdx = 0;
int nodeValue = int.MaxValue;
for (int j = 1; j < N + 1; j++)
{
if (!visited[j] && dist[j] < nodeValue)
{
nodeIdx = j;
nodeValue = dist[j];
}
}
visited[nodeIdx] = true;
for (int j = 0; j < graph[nodeIdx].Count; j++)
{
Node node = graph[nodeIdx][j];
if (dist[node.idx] > dist[nodeIdx] + node.cost)
{
dist[node.idx] = dist[nodeIdx] + node.cost;
}
}
}
}- 정방향 그래프와 역방향 그래프를 만든 뒤, 다익스트라를 2번 수행하면 정답을 구할 수 있다!
출처
[Algorithm] 다익스트라(Dijkstra) 알고리즘 with c#
Shortest Paths(다익스트라 알고리즘 (Dijkstra Algorithm))
오늘은 여기까지~
끗
수수수수퍼노바
