최단 경로 알고리즘이란?
어떻게 하면 가정 적은 비용으로 목적지에 도착할 수 있을까?를 생각하는 알고리즘이다.
1. 다익스트라 알고리즘(Dijkstra Algorithm)
하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 단 모든 간선의 가중치는 0보다 크거나 같아야 한다.
이 알고리즘의 핵심은 지금 까지 찾은 가장 짧은 길을 기억하고 그걸 이용해서 다음 길을 더 쉽게 계산하는 것이다. 즉 지금까지 찾은 가장 짧은 길을 계속 저장해두고 DP처럼 기존에 구한 결과를 재활용한다.
01 작동 과정
distance[] ← ∞, distance[start] ← 0
visited[] ← false
반복:
현재 노드 ← 방문 안 한 노드 중 최소 distance
인접 노드의 거리 갱신
현재 노드 visited = true
종료1. 출발 노드를 설정
2. 출발 노드를 기준으로 각 노드의 거리를 초기화 한다.
3. 아직 방문하지 않는 노드 중에서 가장 거리가 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 갈 수 있는 인접 노드들의 거리 값을 확인하고 기존 거리보다 짧으면 갱신한다.
5. 3~4 과정을 모든 노드를 방문할 때까지 반복한다.
02 예제
1) 초기 상태
distance = [0, ∞, ∞, ∞, ∞, ∞]2) 현재노드
1 → 2 (7), 1 → 3 (9), 1 → 6 (14) 갱신
distance = [0, 7, 9, ∞, ∞, 14]3)현재 노드 2
2 → 4 (7 + 15 = 22)
distance = [0, 7, 9, 22, ∞, 14]4) 현재 노드 3
3 → 4 (9 + 11 = 20 → 더 짧음), 3 → 6 (9 + 2 = 11 → 더 짧음)
distance = [0, 7, 9, 20, ∞, 11]5) 현재 노드 6
6 → 5 (11 + 9 = 20)
distance = [0, 7, 9, 20, 20, 11]6) 현재 노드 4
4 → 5 (20 + 6 = 26 기존보다 큼 → 변경 없음)
distance = [0, 7, 9, 20, 20, 11]7) 현재 노드 5
더이상 갱신 없음
distance = [0, 7, 9, 20, 20, 11]03 작동 과정에 따른 C# 코드
1. 출발 노드를 설정
static void Dijkstra(int[,] graph, int start)2. 출발 노드를 기준으로 각 노드의 거리를 초기화 한다.
int[] distance = new int[n];
for (int i = 0; i < n; i++)
distance[i] = int.MaxValue;
distance[start] = 0;3. 아직 방문하지 않는 노드 중에서 가장 거리가 짧은 노드를 선택한다.
int min = int.MaxValue;
int minIndex = -1; // 현재 가장 짧은 거리값은 가진 노드
// 방문하지 않은 노드 중에서 최단 거리인 노드(minIndex)를 찾는 루프
for (int j = 0; j < n; j++)
{
if (!visited[j] && distance[j] <= min)
{
min = distance[j];
minIndex = j;
}
}4. 해당 노드를 거쳐 갈 수 있는 인접 노드들의 거리 값을 확인하고 기존 거리보다 짧으면 갱신한다.
for (int v = 0; v < n; v++)
{
// 현재 노드 u에서 인접 노드 v로 갈 수 있을 때 그 경로가 더 짧다면 distance[v]를 갱신
if (!visited[v] && graph[u, v] != 0 && distance[u] != int.MaxValue &&
distance[u] + graph[u, v] < distance[v])
{
distance[v] = distance[u] + graph[u, v];
}
}
5. 3~4 과정을 모든 노드를 방문할 때까지 반복한다.
04 C# 코드 전문
// 1. 출발 노드 설정
static void Dijkstra(int[,] graph, int start)
{
int n = graph.GetLength(0);
// 2. 거리 초기화
bool[] visited = new bool[n];
int[] distance = new int[n];
for (int i = 0; i < n; i++) distance[i] = int.MaxValue;
distance[start] = 0;
for (int i = 0; i < n - 1; i++)
{
// 3. 최소 거리 노드 선택
int min = int.MaxValue;
int minIndex = -1;
for (int j = 0; j < n; j++)
{
if (!visited[j] && distance[j] <= min)
{
min = distance[j];
minIndex = j;
}
}
int u = minIndex;
visited[u] = true;
// 4. 인접 노드 거리 갱신
for (int v = 0; v < n; v++)
{
if (!visited[v] && graph[u, v] != 0 &&
distance[u] != int.MaxValue &&
distance[u] + graph[u, v] < distance[v])
{
distance[v] = distance[u] + graph[u, v];
}
}
// 5. 모든 노드를 방문할 때까지 반복
}
}
벨만-포드 알고리즘(Bellman-Ford Algorithm)
음의 가중치를 갖는 간선이 있는 그래프에서도 사용할 수 있는 최단 경로 알고리즘입니다. 음수 사이클이 있는 경우에도 탐지할 수 있습니다.
음수 사이클이란?
사이클(한 반퀴 도는 경로)을 돌고 나서 총 비용이 음수가 되는 경우
01 작동 과정
distance[] ← ∞, distance[start] ← 0
반복 (V - 1회):
모든 간선(u → v) 검사:
distance[v] = min(distance[v], distance[u] + cost)
마지막 1회 더 검사:
갱신 발생 시 → 음수 사이클 존재1. 출발 노드를 설정
2. 시작 노드를 제외한 모든 노드의 거리를 무한대로 초기화한다.
3. 모든 간선을 N-1번 반복하며 검사한다.(N은 노드의 개수)
왜 N-1개인가요? 어떤 경로든 최대 N-1개의 간선만 거쳐서 도달할 수 있다.
예를 들어 노드가 5개이면 가장 멀리 돌아가도 최대 4개의 간선만지나면 도착이 가능하다.
4. A → B로가는 간선이 있고, distance[A] + cost < distance[B]이면 갱신한다.
5. 마지막으로 한 번 더 모든 간선을 검사해서 갱신한다. 갱신이 일어나면 음수 사이클이 존재한다는 뜻이다.
02 예제
실행 이해가 안가서 엑셀에 다 적어보았다 하핳..
1) 초기 상태
distance = [0, ∞, ∞, ∞, ∞]
2) 1번째 반복 (간선 전체 확인)
s → t : 0 + 6 < ∞ distance[1] = 6
s → y : 0 + 7 < ∞ distance[3] = 7
distance = [0, 6, 4, 7, 2]
3) 2번째 반복
t → x : 6 + 5 = 11
t → z : 6 + (-4) = 2
y→ x : 7 + (-3) = 4
distance = [0, 2, 4, 7, 2]
4) 3번째 반복
x→ t : 4 + (-2) = 2
distance = [0, 2, 4, 7, -2]5) 4 번째 반복
distance = [0, 2, 4, 7, -2]03 작동 과정에 따른 C# 코드
1. 출발 노드를 설정
2. 시작 노드를 제외한 모든 노드의 거리를 무한대로 초기화한다.
int[] distance = new int[nodeCount];
for (int i = 0; i < nodeCount; i++)
distance[i] = int.MaxValue;
distance[start] = 0; // 출발 노드는 거리 03. 모든 간선을 N-1번 반복하며 검사한다.(N은 노드의 개수)
for (int i = 0; i < n - 1; i++) // N-1번 반복
{
for (int u = 0; u < n; u++) // u = 출발노드
{
for (int v = 0; v < n; v++) // v = 도착노드
{
// 4번 로직이 여기로
}
}
}왜 N-1개인가요? 어떤 경로든 최대 N-1개의 간선만 거쳐서 도달할 수 있다.
예를 들어 노드가 5개이면 가장 멀리 돌아가도 최대 4개의 간선만지나면 도착이 가능하다.
4. A → B로가는 간선이 있고, distance[A] + cost < distance[B]이면 갱신한다.
if (graph[u, v] != int.MaxValue && distance[u] != int.MaxValue &&
distance[u] + graph[u, v] < distance[v])
{
distance[v] = distance[u] + graph[u, v];
}조건문 설명
graph[u, v] != int.MaxValue - 간선이 실제로 존재하는지 체크
distance[u] != int.MaxValue - 시작노드와 이어져있는지 체크
distance[u] + graph[u, v] < distance[v] - u를 거쳐서 v로 가는게 전에 구했던 경로보다 짧은지
5. 마지막으로 한 번 더 모든 간선을 검사해서 음수 사이클이 존재하는지 확인
bool hasNegativeCycle = false;
for (int u = 0; u < n; u++)
{
for (int v = 0; v < n; v++)
{
if (graph[u, v] != int.MaxValue && distance[u] != int.MaxValue &&
distance[u] + graph[u, v] < distance[v])
{
hasNegativeCycle = true;
break;
}
}
}05 코드 전문
static void BellmanFord(int[,] graph, int start)
{
int n = graph.GetLength(0);
int[] distance = new int[n];
// 2. 거리 초기화
for (int i = 0; i < n; i++)
distance[i] = int.MaxValue;
distance[start] = 0;
// 3. 모든 간선을 N-1번 반복
for (int i = 0; i < n - 1; i++)
{
for (int u = 0; u < n; u++)
{
for (int v = 0; v < n; v++)
{
// 4. 값 갱신
if (graph[u, v] != int.MaxValue && distance[u] != int.MaxValue &&
distance[u] + graph[u, v] < distance[v])
{
distance[v] = distance[u] + graph[u, v];
}
}
}
}
// 5. 음수 사이클 확인
bool hasNegativeCycle = false;
for (int u = 0; u < n; u++)
{
for (int v = 0; v < n; v++)
{
if (graph[u, v] != int.MaxValue && distance[u] != int.MaxValue &&
distance[u] + graph[u, v] < distance[v])
{
hasNegativeCycle = true;
break;
}
}
}
}
다익스트라 vs 벨만-포드
다익스트라
특징 : 방문한 정점 중에서 가장 가까운 노드부터 순서대로 확장
예를 들어 배달 경로처럼 차례차례 가까운 집부터 배달
시간복잡도 : 우선순위큐를 사용하는 경우 O((V + E) log V), 사용하지 않는 경우 O(V^2)
벨만-포드
특징 : 모든 간선을 무작위로 반복해서 살펴보고 더 짧은 길을 선택
예를 들어 계획없이 길을 걷다가 더 짧은 경로를 찾으면 언제든 새로운 경로로 가기
시간 복잡도 : O(V × E)
A* 알고리즘 (A-star Algorithm)
휴리스틱 함수를 사용하여 각 정점까지의 예상 비용을 계산하고, 가장 낮은 예상 비용을 가진 정점을 선택하여 탐색합니다.
01 작동 과정
OPEN ← 시작 노드
CLOSED ← 비어 있음
반복:
current ← f(n) 가장 낮은 노드
목표이면 종료
이웃 노드 확인:
갈 수 없는 곳/이미 본 곳 무시
더 짧은 경로면 g, f 갱신 + parent 설정
처음 본 노드면 OPEN에 추가
current → CLOSED에 이동1. 시작 노드를 OPEN리스트에 넣는다.
OPEN = 탐색 예정인 후보 노드들
CLOSED = 탐색이 끝난 노드들
2. OPEN에서 f(n)이 가장 낮은 노드를 꺼낸다.
g(n) = 시작점에서 현재까지 온 실제거리
h(n) = 현재에서 목표까지의 예상 거리
f(n) = g(n) + h(n)
이 노드를 현재노드라 칭하고 OPEN에서 제거한 다음 CLOED에 넣는다.
3. 목표 지점인지 확인
current 노드가 목표지점이면 경로를 복원해서 반환하고 끝
4. current노드의 이웃노드들 확인
1) 벽이거나 이미 CLOSED에 있는 노드면 건너뛴다.
2) 현재 노드를 거쳐서 가는 경로가 더 짧거나 아직 OPEN에 등록된 적이 없다면
g(n) 갱신: 더 짧은 거리로 도달했다면 거리 갱신
h(n) 계산: 휴리스틱(목표까지 예상 거리) 계산
f(n) 계산: g + h
parent 설정: 어디서 왔는지 기록 (경로 복원용)
OPEN에 등록: 처음 보는 노드였다면
5. OPEN이 빌때까지 반복
OPEN이 완전히 비었는데 도달 못했다면 경로없음
02 예시
0단계 : 초록색(시작)점에서 근처 노드 탐색
Start → a (거리 1.5) → g(a) = 1.5, f(a) = 1.5 + 4 = 5.5
Start → d (거리 2.0) → g(d) = 2.0, f(d) = 2.0 + 4.5 = 6.5
OPEN = {a(5.5), d(6.5)}
f가 가장 낮은 a선택
1단계 : a 선택(f=5.5)
a → b (거리 2.0)
g(b) = g(a) + 2 = 1.5 + 2 = 3.5
h(b) = 2
f(b) = 3.5 + 2 = 5.5
OPEN = {d (6.5), b (5.5)}f가 가장 낮은 b선택
2단계 b선택(f=5.5)
b → c (3.0)
g(c) = 3.5 + 3 = 6.5
h(c) = 4
f(c) = 6.5 + 4 = 10.5
OPEN = {d (6.5), c (10.5)}
f가 가장 낮은 d 선택
3단계 d선택(f=6.5)
d → e (거리 3.0)
g(e) = 2.0 + 3.0 = 5.0, h(e) = 2
f(e) = 7.0
OPEN = {c(10.5), e(7.0)} e → Goal (거리 2.0)
g(Goal) = 5.0 + 2.0 = 7.0, h(Goal) = 0
f(Goal) = 7.0
그래서 최종 경로
Start → d → e → Goal03 작동 과정에 따른 C# 코드
public class Node
{
public int X, Y;
public int G; // 지금까지의 거리
public int H; // 목적지까지의 예상 거리
public int F => G + H; // 총 비용
public Node Parent;
public Node(int x, int y)
{
X = x;
Y = y;
}
public override bool Equals(object obj)
{
if (obj is Node other)
{
return this.X == other.X && this.Y == other.Y;
}
return false;
}
public override int GetHashCode()
{
return (X, Y).GetHashCode();
}
}1. 시작 노드를 OPEN리스트에 넣는다.
OPEN = 탐색 예정인 후보 노드들
CLOSED = 탐색이 끝난 노드들
var openSet = new List<Node>(); // OPEN = 탐색 예정 노드들
var closedSet = new HashSet<Node>(); // CLOSED = 탐색이 끝난 노드들
start.G = 0;
start.H = Heuristic(start, goal);
openSet.Add(start); // 시작 노드를 OPEN에 등록2. OPEN에서 f(n)이 가장 낮은 노드를 꺼낸다.
g(n) = 시작점에서 현재까지 온 실제거리
h(n) = 현재에서 목표까지의 예상 거리
f(n) = g(n) + h(n)
이 노드를 현재노드라 칭하고 OPEN에서 제거한 다음 CLOED에 넣는다.
Node current = openSet[0];
foreach (var node in openSet)
if (node.F < current.F)
current = node;
openSet.Remove(current);
closedSet.Add(current); // 탐색 완료 → CLOSED에 넣기3. 목표 지점인지 확인
current 노드가 목표지점이면 경로를 복원해서 반환하고 끝
if (current.X == goal.X && current.Y == goal.Y)
{
// 경로 복원
var path = new List<Node>();
while (current != null)
{
path.Add(current);
current = current.Parent;
}
path.Reverse();
return path;
}4. current노드의 이웃노드들 확인
1) 벽이거나 이미 CLOSED에 있는 노드면 건너뛴다.
2) 현재 노드를 거쳐서 가는 경로가 더 짧거나 아직 OPEN에 등록된 적이 없다면
g(n) 갱신: 더 짧은 거리로 도달했다면 거리 갱신
h(n) 계산: 휴리스틱(목표까지 예상 거리) 계산
f(n) 계산: g + h
foreach (var neighbor in GetNeighbors(current, grid))
{
// 1) 벽이거나 CLOSED에 있으면 skip
if (closedSet.Contains(neighbor)) continue;
int tentativeG = current.G + 1; // 인접 노드까지 거리 (기본적으로 1로 가정)
// 2) 더 짧은 경로거나, 처음 보는 노드라면
bool inOpen = openSet.Contains(neighbor);
if (!inOpen || tentativeG < neighbor.G)
{
neighbor.G = tentativeG;
neighbor.H = Heuristic(neighbor, goal);
neighbor.Parent = current;
if (!inOpen)
openSet.Add(neighbor); // 처음 보는 노드라면 등록
}
}parent 설정: 어디서 왔는지 기록 (경로 복원용)
OPEN에 등록: 처음 보는 노드였다면
5. OPEN이 빌때까지 반복
OPEN이 완전히 비었는데 도달 못했다면 경로없음
while (openSet.Count > 0)
{
// 위 과정 반복
...
}
return null; // OPEN이 비었는데 목표 도달 못했으면 → 경로 없음04 코드 전문
using System;
using System.Collections.Generic;
public class AStar
{
public class Node
{
public int X, Y;
public int G; // 지금까지의 거리
public int H; // 휴리스틱 (예상 거리)
public int F => G + H; // 총 비용
public Node Parent;
public Node(int x, int y)
{
X = x;
Y = y;
}
public override bool Equals(object obj)
{
if (obj is Node other)
{
return this.X == other.X && this.Y == other.Y;
}
return false;
}
public override int GetHashCode()
{
return (X, Y).GetHashCode();
}
}
static int Heuristic(Node a, Node b)
{
// 맨해튼 거리
return Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y);
}
static List<Node> GetNeighbors(Node node, int[,] grid)
{
var neighbors = new List<Node>();
int[] dx = { 0, 1, 0, -1 };
int[] dy = { -1, 0, 1, 0 };
for (int i = 0; i < 4; i++)
{
int nx = node.X + dx[i];
int ny = node.Y + dy[i];
if (nx >= 0 && ny >= 0 && nx < grid.GetLength(0) && ny < grid.GetLength(1))
{
if (grid[nx, ny] == 0) // 0은 이동 가능, 1은 벽
neighbors.Add(new Node(nx, ny));
}
}
return neighbors;
}
public static List<Node> FindPath(int[,] grid, Node start, Node goal)
{
var openSet = new List<Node>();
var closedSet = new HashSet<Node>();
start.G = 0;
start.H = Heuristic(start, goal);
openSet.Add(start);
while (openSet.Count > 0)
{
// f 값이 가장 작은 노드 선택
Node current = openSet[0];
foreach (var node in openSet)
if (node.F < current.F) current = node;
if (current.X == goal.X && current.Y == goal.Y)
{
// 경로 추적
var path = new List<Node>();
while (current != null)
{
path.Add(current);
current = current.Parent;
}
path.Reverse();
return path;
}
openSet.Remove(current);
closedSet.Add(current);
foreach (var neighbor in GetNeighbors(current, grid))
{
if (closedSet.Contains(neighbor)) continue;
int tentativeG = current.G + 1;
bool inOpen = openSet.Contains(neighbor);
if (!inOpen || tentativeG < neighbor.G)
{
neighbor.G = tentativeG;
neighbor.H = Heuristic(neighbor, goal);
neighbor.Parent = current;
if (!inOpen)
openSet.Add(neighbor);
}
}
}
return null; // 경로 없음
}
}
'코딩테스트 준비 > 자료구조 & 알고리즘' 카테고리의 다른 글
| 탐색 알고리즘 총 정리(선형,이진탐색,해시탐색) (0) | 2025.04.16 |
|---|---|
| 시간복잡도(빅오표기법)을 왜 알아야할까? (0) | 2025.04.09 |
| C# - 이진 탐색 트리(Binary Search Tree) (0) | 2024.06.11 |
| C# - 배열을 문자열로 바꾸는 방법 (0) | 2024.04.08 |
| 알고리즘 - 그리디(Greedy) 알고리즘 (1) | 2024.03.26 |
댓글