[알고리즘] 32. 최단 거리 기초
지난 글에서는 격자 탐색에 대해 정리했습니다. 이번 글에서는 그래프와 격자 문제에서 자주 등장하는 최단 거리에 대해 알아보겠습니다.
최단 거리는 말 그대로 어떤 시작점에서 목표 지점까지 가는 데 필요한 가장 짧은 거리입니다. 알고리즘 문제에서는 최소 이동 횟수, 최소 비용, 가장 빠른 경로 같은 형태로 자주 등장합니다.
최단 거리는 시작점에서 목표 지점까지 도달하는 여러 경로 중 가장 짧은 경로의 길이를 의미합니다.
1. 최단 거리란?
최단 거리는 여러 경로 중에서 가장 짧은 경로를 찾는 개념입니다. 예를 들어 1번 정점에서 4번 정점으로 이동한다고 생각해보겠습니다.
1 --- 2 --- 4
\ /
--- 3 ---1번에서 4번으로 가는 경로는 여러 가지가 있을 수 있습니다.
- 1 → 2 → 4
- 1 → 3 → 4
두 경로 모두 간선을 2번 지나므로 거리는 2입니다. 이처럼 시작점에서 목표 지점까지 가는 데 필요한 최소 이동 횟수를 구하는 것이 최단 거리 문제의 기본입니다.
최단 거리 문제는 “어떻게 가야 가장 적게 이동하는가?”를 묻는 문제입니다.
2. 최단 거리 문제가 나오는 상황
최단 거리 문제는 다양한 형태로 등장합니다. 문제 표현은 달라도 핵심은 최소 이동이나 최소 비용을 구하는 것입니다.
- 미로에서 출구까지 최소 이동 횟수 구하기
- 지도에서 목적지까지 가장 짧은 거리 구하기
- 그래프에서 한 정점에서 다른 정점까지 최소 간선 수 구하기
- 게임 맵에서 캐릭터가 목표 지점까지 가는 최소 이동 수 구하기
- 도시 사이의 최소 이동 비용 구하기
- 네트워크에서 가장 빠른 전달 경로 구하기
이때 중요한 것은 모든 최단 거리 문제가 같은 알고리즘으로 풀리지는 않는다는 점입니다. 간선의 비용이 있는지 없는지에 따라 풀이가 달라집니다.
3. 가중치가 없는 그래프의 최단 거리
간선마다 비용이 따로 없고, 한 번 이동할 때마다 비용이 모두 1이라면 BFS를 사용할 수 있습니다.
1 --- 2 --- 4
|
3위 그래프에서 간선 하나를 지날 때마다 거리 1이라고 생각하면 됩니다. 이런 문제에서는 시작점에서 가까운 정점부터 차례대로 방문하는 BFS가 최단 거리를 보장합니다.
간선의 비용이 모두 같다면 BFS로 최단 거리를 구할 수 있습니다.
4. 왜 BFS가 최단 거리를 보장할까요?
BFS는 시작점에서 가까운 정점부터 차례대로 탐색합니다. 먼저 거리 1인 정점을 방문하고, 그다음 거리 2인 정점, 그다음 거리 3인 정점을 방문합니다.
시작점
→ 거리 1인 정점들
→ 거리 2인 정점들
→ 거리 3인 정점들따라서 어떤 정점에 처음 도착한 순간의 거리가 그 정점까지의 최단 거리입니다. 나중에 다시 도착하는 경로는 같거나 더 긴 경로가 됩니다.
그래서 BFS에서는 한 번 방문한 정점을 다시 방문하지 않아도 됩니다. 처음 방문한 거리가 이미 최단 거리이기 때문입니다.
BFS에서는 처음 방문한 순간의 거리가 최단 거리입니다.
5. distance 배열
최단 거리를 저장할 때는 보통 distance 배열을 사용합니다. distance[i]는 시작점에서 i번 정점까지의 거리를 의미합니다.
distance[1] = 0
distance[2] = 1
distance[3] = 1
distance[4] = 2시작점의 거리는 0입니다. 시작점에서 한 번 이동해서 갈 수 있는 정점의 거리는 1입니다. 그다음 정점의 거리는 2가 됩니다.
아직 방문하지 않은 정점은 -1로 표시하는 경우가 많습니다.
int[] distance = new int[n + 1];
Arrays.fill(distance, -1);distance 배열은 방문 여부와 거리 정보를 함께 표현할 수 있습니다.
6. 그래프 BFS 최단 거리 코드
가중치가 없는 그래프에서 BFS로 최단 거리를 구하는 기본 코드는 다음과 같습니다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
static ArrayList<Integer>[] graph;
static int[] distance;
public static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
Arrays.fill(distance, -1);
queue.offer(start);
distance[start] = 0;
while (!queue.isEmpty()) {
int current = queue.poll();
for (int next : graph[current]) {
if (distance[next] == -1) {
distance[next] = distance[current] + 1;
queue.offer(next);
}
}
}
}여기서 distance[next] == -1은 아직 방문하지 않은 정점이라는 뜻입니다. 다음 정점을 처음 방문할 때 현재 정점의 거리보다 1 큰 값을 저장합니다.
distance[next] = distance[current] + 17. 그래프 최단 거리 예시
다음 그래프에서 1번 정점부터 각 정점까지의 최단 거리를 구해보겠습니다.
1 --- 2 --- 4
|
3연결 관계는 다음과 같습니다.
| 정점 | 연결된 정점 |
|---|---|
| 1 | 2, 3 |
| 2 | 1, 4 |
| 3 | 1 |
| 4 | 2 |
1번에서 시작하면 거리 배열은 다음과 같이 채워집니다.
distance[1] = 0
distance[2] = 1
distance[3] = 1
distance[4] = 21번에서 4번으로 가려면 1 → 2 → 4로 이동해야 하므로 최단 거리는 2입니다.
8. 격자에서 최단 거리
최단 거리 문제는 2차원 격자에서도 자주 등장합니다. 대표적인 예가 미로 문제입니다.
1 1 0
0 1 1
0 0 11은 이동 가능한 칸, 0은 벽이라고 하겠습니다. 시작점에서 목적지까지 이동할 때 최소 몇 번 이동해야 하는지 구하려면 BFS를 사용할 수 있습니다.
격자에서도 한 번 이동할 때 비용이 모두 1이라면 BFS가 최단 거리를 보장합니다.
격자 최단 거리 문제에서도 이동 비용이 모두 같다면 BFS를 사용합니다.
9. 격자 최단 거리에서 방향 배열
격자에서 상하좌우로 이동할 때는 방향 배열을 사용합니다.
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};현재 위치가 (x, y)라면 다음 위치는 다음처럼 계산합니다.
int nx = x + dx[dir];
int ny = y + dy[dir];다음 위치를 계산한 뒤에는 항상 범위 체크를 먼저 해야 합니다.
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}10. 격자 BFS 최단 거리 코드
2차원 격자에서 BFS로 최단 거리를 구하는 기본 코드는 다음과 같습니다.
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
static int[][] map;
static int[][] distance;
static int n;
static int m;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void bfs(int startX, int startY) {
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
Arrays.fill(distance[i], -1);
}
queue.offer(new int[] {startX, startY});
distance[startX][startY] = 0;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}
if (distance[nx][ny] != -1) {
continue;
}
if (map[nx][ny] == 0) {
continue;
}
distance[nx][ny] = distance[x][y] + 1;
queue.offer(new int[] {nx, ny});
}
}
}distance[nx][ny]가 -1이 아니라면 이미 방문한 칸입니다. 따라서 distance 배열은 거리 저장과 방문 체크 역할을 동시에 합니다.
11. 도달할 수 없는 경우
최단 거리 문제에서는 목적지에 도달할 수 없는 경우도 있습니다. 이 경우 distance 값이 끝까지 -1로 남습니다.
distance[target] == -1 → 도달할 수 없음격자에서도 마찬가지입니다. 목적지 좌표가 (endX, endY)라면 다음처럼 확인할 수 있습니다.
if (distance[endX][endY] == -1) {
System.out.println("도달할 수 없습니다.");
} else {
System.out.println(distance[endX][endY]);
}문제에서 도달할 수 없는 경우 -1을 출력하라고 하는 경우가 많습니다. 이런 조건을 놓치지 않아야 합니다.
최단 거리 문제에서는 도달 불가능한 경우도 반드시 처리해야 합니다.
12. 가중치가 있는 그래프는 어떻게 할까요?
모든 간선의 비용이 같다면 BFS를 사용할 수 있습니다. 하지만 간선마다 비용이 다르면 일반 BFS로는 최단 거리를 구할 수 없습니다.
A -- 1 -- B
A -- 10 -- C
B -- 1 -- CA에서 C로 가는 경로를 생각해보겠습니다. 간선 개수만 보면 A → C는 한 번에 갈 수 있습니다. 하지만 비용은 10입니다. 반면 A → B → C는 간선을 두 번 지나지만 비용은 2입니다.
일반 BFS는 간선 개수를 기준으로 가까운 정점을 먼저 방문합니다. 그래서 비용이 서로 다른 그래프에서는 적합하지 않습니다.
간선마다 비용이 다르면 BFS가 아니라 다익스트라 같은 알고리즘을 고려해야 합니다.
13. 최단 거리 알고리즘 선택 기준
최단 거리 문제는 그래프의 조건에 따라 사용하는 알고리즘이 달라집니다. 입문 단계에서는 아래 기준을 먼저 기억하면 좋습니다.
| 상황 | 사용 알고리즘 |
|---|---|
| 간선 비용이 모두 같음 | BFS |
| 간선 비용이 다르고 음수가 없음 | 다익스트라 |
| 모든 정점 쌍의 최단 거리 필요 | 플로이드 워셜 |
이번 글에서는 BFS를 이용한 기본 최단 거리만 다루었습니다. 다익스트라와 플로이드 워셜은 이후 그래프 심화에서 따로 정리할 수 있습니다.
14. 최단 거리 문제에서 자주 하는 실수
최단 거리 문제를 풀 때는 아래 실수를 조심해야 합니다.
- 간선 비용이 다른데 BFS를 사용하는 경우
- distance 배열을 초기화하지 않는 경우
- 시작점 거리를 0으로 설정하지 않는 경우
- 방문하지 않은 값을 -1이나 INF로 구분하지 않는 경우
- 이미 방문한 정점을 다시 큐에 넣는 경우
- 격자 문제에서 범위 체크를 하지 않는 경우
- 도달할 수 없는 경우를 처리하지 않는 경우
- 이동 횟수를 칸 수와 혼동하는 경우
특히 문제에서 “몇 칸을 지나야 하는지”와 “몇 번 이동해야 하는지”를 구분해야 합니다. 시작 칸을 거리 0으로 볼지, 1로 볼지는 문제 조건에 따라 달라질 수 있습니다.
최단 거리 문제에서는 시작점의 거리 기준을 문제 조건에 맞게 잡아야 합니다.
15. 최단 거리의 시간복잡도
BFS를 이용한 최단 거리 계산은 그래프의 모든 정점과 간선을 한 번씩 확인합니다. 정점 수를 V, 간선 수를 E라고 하면 시간복잡도는 O(V + E)입니다.
| 구분 | 시간복잡도 |
|---|---|
| 그래프 BFS 최단 거리 | O(V + E) |
| 격자 BFS 최단 거리 | O(N × M) |
격자에서는 각 칸을 하나의 정점처럼 볼 수 있습니다. 행이 N개, 열이 M개라면 전체 칸의 수는 N × M이므로 시간복잡도는 O(N × M)입니다.
16. 정리
이번 글에서는 최단 거리 기초에 대해 정리했습니다.
- 최단 거리는 시작점에서 목표 지점까지의 가장 짧은 거리이다.
- 간선 비용이 모두 같다면 BFS로 최단 거리를 구할 수 있다.
- BFS는 가까운 정점부터 방문하기 때문에 처음 방문한 거리가 최단 거리이다.
- distance 배열은 거리 저장과 방문 체크 역할을 함께 할 수 있다.
- 방문하지 않은 정점이나 칸은 보통 -1로 초기화한다.
- 격자 최단 거리 문제에서도 BFS를 자주 사용한다.
- 도달할 수 없는 경우 distance 값이 -1로 남는다.
- 간선마다 비용이 다르면 BFS 대신 다익스트라 같은 알고리즘을 고려해야 한다.
최단 거리 문제는 그래프와 격자 탐색의 핵심 유형입니다. 처음에는 BFS로 풀 수 있는 조건을 정확히 구분하는 것이 중요합니다. 간선의 비용이 모두 같다면 BFS, 비용이 다르다면 다른 최단 거리 알고리즘을 고려해야 합니다.
최단 거리 기초의 핵심은 비용이 모두 같은 그래프에서는 BFS로 가장 짧은 이동 횟수를 구할 수 있다는 점입니다.
다음 글 예고
다음 글부터는 정렬과 구간 처리 영역으로 넘어갑니다. 다음 글에서는 정렬 알고리즘 개념에 대해 알아보겠습니다.
오름차순과 내림차순, 정렬이 필요한 이유, 선택 정렬과 버블 정렬 같은 기본 정렬 흐름을 차근차근 정리해보겠습니다.
'Problem Solving > Algorithm' 카테고리의 다른 글
| [알고리즘] 34. Java 정렬 사용법 (0) | 2026.07.17 |
|---|---|
| [알고리즘] 33. 정렬 알고리즘 개념 (0) | 2026.07.16 |
| [알고리즘] 31. 격자 탐색 (0) | 2026.07.14 |
| [알고리즘] 30. 방문 배열 (0) | 2026.07.13 |
| [알고리즘] 29. BFS 너비 우선 탐색 (0) | 2026.07.12 |