728x90
반응형
그래프 탐색 / 최단거리 알고리즘 정리
그래프 문제를 보면 먼저 “무엇을 구하는 문제인지”를 판단해야 한다.
| 문제 특징 | 사용 알고리즘 |
|---|---|
| 가능한 경로를 전부 탐색 | DFS |
| 연결 요소 / 네트워크 개수 | DFS / BFS |
| 가중치가 없는 최단거리 | BFS |
| 모든 간선 비용이 동일한 최단거리 | BFS |
| 가중치가 0 또는 1 | 0-1 BFS |
| 양수 가중치 + 한 출발점에서 최단거리 | 다익스트라 |
| 모든 정점 → 모든 정점 최단거리 | 플로이드-워셜 |
핵심은 다음과 같다.
모든 경우를 직접 돌아본다 → DFS
몇 번 이동했는지가 중요하다
모든 이동 비용이 동일하다 → BFS
간선마다 이동 비용이 다르다
한 지점에서 최단거리 → 다익스트라
모든 노드 사이의 최단거리가 필요하다
→ 플로이드-워셜1. 가중치 그래프 저장
예를 들어 다음 그래프가 있다고 하자.
1 --2--> 2
1 --5--> 3
2 --1--> 3
2 --4--> 4
3 --1--> 4가중치 그래프는 보통 다음처럼 저장한다.
vector<vector<pair<int,int>>> graph(n + 1);pair의 의미는:
{다음 노드, 가중치}예를 들어:
graph[1].push_back({2, 2});는
1 → 2
비용 = 2라는 뜻이다.
2. DFS — 가능한 경로를 전부 탐색
DFS는 최단거리 전용 알고리즘이 아니다.
다음과 같은 문제에서 사용하기 좋다.
모든 경로의 개수
특정 조건을 만족하는 경로
경로별 비용 합
경로의 최대/최소를 완전탐색예를 들어:
1 --5--> 2 --4--> 4
\
--2--> 3 --10-> 41에서 4까지 가능한 경로의 비용을 모두 탐색한다면:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n = 4;
int target = 4;
vector<vector<pair<int,int>>> graph(n + 1);
vector<int> visited(n + 1, 0);
int minCost = 1e9;
void DFS(int node, int sum){
// 목적지 도착
if(node == target){
minCost = min(minCost, sum);
return;
}
// 현재 노드와 연결된 곳 탐색
for(auto next : graph[node]){
int nextNode = next.first;
int weight = next.second;
if(visited[nextNode] == 0){
visited[nextNode] = 1;
DFS(nextNode, sum + weight);
// 다른 경로 탐색을 위해 복구
visited[nextNode] = 0;
}
}
}
int main(){
graph[1].push_back({2, 5});
graph[1].push_back({3, 2});
graph[2].push_back({4, 4});
graph[3].push_back({4, 10});
visited[1] = 1;
DFS(1, 0);
cout << minCost;
return 0;
}핵심은:
DFS(nextNode, sum + weight);이다.
DFS(node, sum)
node = 현재 위치
sum = 지금까지 누적된 가중치즉:
현재 노드
↓
갈 수 있는 노드 선택
↓
가중치 누적
↓
DFS
↓
돌아오면 visited 복구단, 노드와 간선 수가 많을 때 최단거리를 DFS로 모든 경로 탐색하는 것은 매우 비효율적이다.
3. BFS — 가중치가 동일한 최단거리
BFS는 현재 위치에서:
거리 1
↓
거리 2
↓
거리 3순으로 탐색한다.
그래서 한 번 이동할 때의 비용이 모두 동일하면 최단거리를 보장한다.
대표적으로 2차원 미로 문제가 있다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n = 5;
vector<vector<int>> graph(n);
vector<int> dist(n, -1);
void BFS(int start){
queue<int> q;
q.push(start);
dist[start] = 0;
while(!q.empty()){
int cur = q.front();
q.pop();
for(int next : graph[cur]){
// 처음 방문한 경우
if(dist[next] == -1){
dist[next] = dist[cur] + 1;
q.push(next);
}
}
}
}핵심:
dist[next] = dist[cur] + 1;모든 간선의 이동 비용이 1이라고 생각하는 것이다.
4. 일반 가중치에서 BFS를 쓰면 안 되는 이유
다음 그래프를 보자.
1 --------100--------> 4
1 --1--> 2 --1--> 3 --1--> 4BFS는 간선 개수를 기준으로 보면:
1 → 4가 가장 가깝다.
간선이 1개이기 때문이다.
하지만 실제 비용은:
1 → 4
= 100반면:
1 → 2 → 3 → 4
= 1 + 1 + 1
= 3이다.
따라서 간선마다 비용이 다르면 일반 BFS를 사용할 수 없다.
이때 사용하는 것이 다익스트라다.
5. 다익스트라 — 한 출발점에서 최단거리
다익스트라는 다음 조건에서 사용한다.
간선마다 비용이 다름
+
가중치가 음수가 아님
+
한 시작점에서 다른 노드들까지 최단거리핵심 아이디어:
현재까지 가장 비용이 작은 노드를 선택
↓
그 노드를 거쳐서 다른 노드로 가봄
↓
기존 거리보다 짧으면 갱신
↓
계속 반복그래서 최소 힙(priority_queue)을 사용한다.
C++ 기본 코드
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
int n = 5;
vector<vector<pair<int,int>>> graph(n + 1);
vector<int> dijkstra(int start){
const int INF = INT_MAX;
// dist[i]
// start → i 최소 비용
vector<int> dist(n + 1, INF);
// {비용, 노드}
// 최소 비용부터 꺼내기
priority_queue<
pair<int,int>,
vector<pair<int,int>>,
greater<pair<int,int>>
> pq;
dist[start] = 0;
pq.push({0, start});
while(!pq.empty()){
int cost = pq.top().first;
int node = pq.top().second;
pq.pop();
// 이미 더 짧은 경로를 찾은 상태
if(cost > dist[node]){
continue;
}
for(auto next : graph[node]){
int nextNode = next.first;
int weight = next.second;
int nextCost = cost + weight;
// 기존 거리보다 짧은 경로 발견
if(nextCost < dist[nextNode]){
dist[nextNode] = nextCost;
pq.push({nextCost, nextNode});
}
}
}
return dist;
}
int main(){
graph[1].push_back({2, 2});
graph[1].push_back({3, 5});
graph[2].push_back({3, 1});
graph[2].push_back({4, 4});
graph[3].push_back({4, 1});
graph[4].push_back({5, 3});
vector<int> dist = dijkstra(1);
for(int i = 1; i <= n; i++){
cout << "1 -> " << i
<< " : " << dist[i] << endl;
}
return 0;
}예를 들어:
1 --5--> 3
1 --2--> 2 --1--> 3처음에는:
dist[1] = 0
dist[2] = INF
dist[3] = INF1번에서 탐색:
1 → 2 = 2
1 → 3 = 5따라서:
dist[2] = 2
dist[3] = 5우선순위 큐에서는 비용이 작은 2번을 먼저 꺼낸다.
2번을 거쳐 3번으로 가면:
1 → 2 → 3
= 2 + 1
= 3기존:
dist[3] = 5보다 작으므로:
dist[3] = 3으로 갱신한다.
이게 다익스트라의 핵심인 Relaxation(거리 갱신)이다.
if(nextCost < dist[nextNode]){
dist[nextNode] = nextCost;
}6. 다익스트라에서 priority_queue를 쓰는 이유
다익스트라는 항상:
지금까지 발견한 노드 중 가장 비용이 작은 노드
부터 확인해야 한다.
그래서:
priority_queue<
pair<int,int>,
vector<pair<int,int>>,
greater<pair<int,int>>
> pq;를 사용한다.
pair에:
{거리, 노드}순서로 저장해야 거리 기준 최소 힙으로 동작한다.
pq.push({nextCost, nextNode});7. 플로이드-워셜 — 모든 노드 ↔ 모든 노드 최단거리
다익스트라는 보통:
한 출발점 → 모든 노드를 구한다.
반면 플로이드-워셜은:
모든 노드 → 모든 노드의 최단거리를 한 번에 구한다.
예를 들어:
1 → 2 최단거리?
1 → 3 최단거리?
1 → 4 최단거리?
2 → 1 최단거리?
2 → 3 최단거리?
...
전부 필요함이라면 플로이드-워셜을 고려한다.
핵심 공식은:
dist[i][j] =
min(
dist[i][j],
dist[i][k] + dist[k][j]
);의미는:
i → j로 바로 가는 것
vs
i → k → j
k를 거쳐서 가는 것중 더 짧은 것을 선택하는 것이다.
8. 플로이드-워셜 C++ 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int main(){
int n = 4;
vector<vector<int>> dist(
n + 1,
vector<int>(n + 1, INF)
);
// 자기 자신까지 거리 = 0
for(int i = 1; i <= n; i++){
dist[i][i] = 0;
}
// 간선 입력
dist[1][2] = 4;
dist[1][3] = 10;
dist[2][3] = 2;
dist[3][4] = 3;
dist[2][4] = 10;
// k = 거쳐가는 노드
for(int k = 1; k <= n; k++){
// i = 출발 노드
for(int i = 1; i <= n; i++){
// j = 도착 노드
for(int j = 1; j <= n; j++){
dist[i][j] = min(
dist[i][j],
dist[i][k] + dist[k][j]
);
}
}
}
// 결과 출력
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(dist[i][j] == INF)
cout << "INF ";
else
cout << dist[i][j] << " ";
}
cout << endl;
}
return 0;
}여기서 가장 중요한 건 반복문 순서다.
for(int k = 1; k <= n; k++) // 경유지
for(int i = 1; i <= n; i++) // 출발
for(int j = 1; j <= n; j++) // 도착k → i → j 순서로 외우면 된다.
9. 플로이드-워셜 예제 이해
처음에:
1 → 3 = 10이라고 하자.
그런데:
1 → 2 = 4
2 → 3 = 2라면:
1 → 2 → 3
= 4 + 2
= 6이 된다.
그래서:
기존
dist[1][3] = 10
2번을 거쳐서
dist[1][2] + dist[2][3]
= 4 + 2
= 6따라서:
dist[1][3] = 6으로 갱신한다.
즉 플로이드-워셜은:
“k번 노드를 중간에 거쳐가면 더 싸지는가?”
를 모든 i, j, k에 대해 확인하는 알고리즘이다.
10. 다익스트라 vs 플로이드-워셜
| 구분 | 다익스트라 | 플로이드-워셜 |
|---|---|---|
| 목적 | 한 출발점 기준 최단거리 | 모든 노드 간 최단거리 |
| 자료구조 | 인접리스트 + 우선순위 큐 | 2차원 거리 배열 |
| 시간복잡도 | 보통 O((V+E) log V) |
O(V³) |
| 가중치 | 음수 불가 | 음수 가능, 음수 사이클은 별도 고려 |
| 노드 수가 큼 | 유리 | 불리 |
| 구현 | 조금 복잡 | 매우 단순 |
그래서 문제에서:
"1번 도시에서 모든 도시까지"라고 하면 보통 다익스트라.
"각 도시에서 다른 모든 도시까지"라고 하면 플로이드-워셜을 먼저 생각하면 된다.
11. DFS / BFS / 다익스트라 / 플로이드 한 번에 구분
그래프 문제
│
├─ 모든 경우/경로 탐색?
│ ↓
│ DFS
│
└─ 최단거리?
│
├─ 모든 간선 비용 동일
│ ↓
│ BFS
│
├─ 가중치 서로 다름
│ │
│ ├─ 한 출발점
│ │ ↓
│ │ 다익스트라
│ │
│ └─ 모든 노드 ↔ 모든 노드
│ ↓
│ 플로이드-워셜이 프레임을 기억하면 대부분의 기본 그래프 문제에서 알고리즘 선택이 가능하다.
12. 코드 형태 비교
DFS:
DFS(node, sum){
for(연결된 노드){
if(방문 안 함){
방문;
DFS(next, sum + weight);
방문 취소;
}
}
}BFS:
queue에 시작점;
while(queue가 안 빔){
현재 노드 꺼냄;
for(연결된 노드){
if(처음 방문){
거리 = 현재거리 + 1;
queue에 넣기;
}
}
}다익스트라:
priority_queue에 시작점;
while(pq가 안 빔){
가장 비용이 작은 노드 꺼냄;
for(연결된 노드){
새로운 비용 계산;
if(기존보다 작음){
거리 갱신;
pq에 넣기;
}
}
}플로이드:
for(k)
for(i)
for(j)
dist[i][j] =
min(
dist[i][j],
dist[i][k] + dist[k][j]
);13. 프로그래머스에서 같이 풀어볼 문제
| 문제 | 알고리즘 | 핵심 |
|---|---|---|
| 타겟 넘버 | DFS | 선택 분기 |
| 네트워크 | DFS/BFS | 연결 요소 |
| 게임 맵 최단거리 | BFS | 2차원 최단거리 |
| 가장 먼 노드 | BFS | 그래프 최단거리 |
| 부대복귀 | BFS | 동일 가중치 최단거리 |
| 배달 | 다익스트라 | 가중치 그래프 최단거리 |
| 합승 택시 요금 | 다익스트라 / 플로이드 | 여러 지점 간 최단거리 |
| 등산코스 정하기 | 변형 다익스트라 | 경로 최대 간선 최소화 |
특히 공부 순서는:
네트워크
↓
게임 맵 최단거리
↓
가장 먼 노드
↓
배달
↓
합승 택시 요금정도로 이어가면 좋다.
최종 요약
DFS
→ 가능한 경로를 직접 전부 탐색
BFS
→ 가중치가 동일한 최단거리
다익스트라
→ 양수 가중치 그래프에서
한 시작점 기준 최단거리
플로이드-워셜
→ 모든 노드 사이의 최단거리가장 중요한 판단 기준은:
“최단거리인가?”, “가중치가 같은가?”, “출발점 하나만 필요한가 아니면 모든 노드 쌍이 필요한가?”
728x90
반응형
'coding test - C++ > 기본기문제' 카테고리의 다른 글
| [C++] 이분탐색 (0) | 2026.10.01 |
|---|---|
| [C++] 그래프, 인접행렬, 최단거리 BFS (0) | 2026.09.29 |
| [C++] 미로탐색 - DFS 경로 수 구하기 (0) | 2026.09.29 |
| [C++] 경로 탐색 (DFS) (0) | 2026.09.28 |
| [C++] 수식 만들기 - DFS (0) | 2026.09.28 |