최단 경로 basic
최단 경로 알고리즘을 하기 전에 백트레킹을 이용해서 최단 경로를 찾는 코드를 짜 보자!
그래프 용어
그래프에서 사용하는 용어는 다음과 같다.
정점 : 한 지점을 나타낸다.
간선 : 정점과 정점을 연결한 것을 나타낸다.
가중치 간선 : 정점과 정점 사이를 이동하는데 드는 비용이나 힘이 표시된 간선
그래프의 표현
그래프는 크게 2가지로 표현할 수 있다.
- 인접행렬
- 인접리스트
배열로 그래프를 구현해 놓은 것을 인접행렬이라고 부른다. 구현은 매우 간단하다.
두 정점의 연결 관계가 입력되었을 때, (vertex1, vertex2)와 (vertex2, vertex1)에 체크 또는 가중치를 넣어주면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
//인접행렬에 체크하기
while(m--) {
int a, b; cin >> a >> b;
G[a][b] = G[b][a] = 1;
}
//인접행렬에 가중치 넣기
while(m--) {
int a, b, w; cin >> a >> b >> w;
G[a][b] = G[b][a] = w;
}
|
cs |
vector를 이용해 그래프를 구현해 놓은 것을 인접리스트라고 부른다.
주로 그래프 문제를 해결할 때 가장 많이 사용하는 방법으로 인접행렬에 비해 처리가 간단하다.
구현은 다음과 같이 할 수 있다.
|
1
2
3
4
5
6
7
8
9
|
//인접리스트 구현
vector<int> G[110];
while(m--) {
int a, b; cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
|
cs |
그래프를 이용한 최단 경로 구하기
최단 경로를 구하는 방법은 여러가지가 존재하지만!
가장 기초적이고 구현하기 쉬운 Backtrack, 즉 역추적을 이용한 최단 경로 구하기를 해 보자.
Backtrack, 역추적은 말 그대로 아니다 싶으면 다시 돌아가는 방법으로 재귀로 구현하는 것이 일반적이다.
이를 설명하기 위한 예시로 촌수 계산 문제를 준비하였다.
촌수 계산 문제에 있는 예시를 그래프로 그려보면 다음과 같은 그래프가 나오게 된다.
이제 이 그래프를 역추적을 이용해서 탐색을 해 보자!
역추적을 하기 전에 세팅을 몇개 해 줄 것인데...
그래프 구현은 인접행렬을 이용할 것이고, 최소는 ans라는 변수에 저장해 나갈 것인데!
ans를 110으로 해 놓은 것은 절대 나올 수 없는 수를 정해두고 최소가 구해지면 갱신하는 방향으로 코드를 짤 것이기 때문이다.
이제 본격적으로 역추적을 해 보자.
만약 구현된 그래프에 연결되어 있는 것이 확인되고, 해당 정점을 방문한 적이 없다면?
방문했다는 것을 체크해 주고, 재귀를 해당 정점을 돌리면서 촌수를 1 증가시켜 준다.
그리고 선택하지 않는 경우, 즉 방문은 하지 않았지만 방문을 하지 않고 그냥 지나가는 경우도 있을 수 있으므로 체크를 풀어준다.
이 과정을 반복하다가, 도착 정점에 도착하였다면, 저장된 촌수를 갱신해 주면 된다.
여기서 처리를 하나 더해서 연산량을 줄여보자면, 최소 촌수를 넘어버리면 더 이상 연산할 필요가 없으므로 재귀를 멈춰준다.
마지막으로 출력할 때에 ans가 그대로 있다면, 최소 촌수가 존재하지 않는 것이므로 -1을 출력하고 아니면 ans에 저장된 최소 촌수를 출력해 주면 된다.
구현된 코드는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
/*
ID : Literhyeon
LANG : C++
*/
#include <iostream>
#include <vector>
using namespace std;
int x, y, visited[110];
int G[110][110];
int ans = 110;
void dfs(int p, int c) {
if(ans < c) return;
if(p == y) {
if(ans > c) ans = c;
return;
}
for(int i=1; i<=100; i++) {
if(G[p][i] && !visited[i]) {
visited[i] = 1;
dfs(i, c+1);
visited[i] = 0;
}
}
}
int main()
{
int n, m; cin >> n >> x >> y >> m;
while(m--) {
int a, b; cin >> a >> b;
G[a][b] = G[b][a] = 1;
}
dfs(x, 0);
if(ans == 110) {
cout << "-1\n";
} else {
cout << ans << "\n";
}
return 0;
}
|
cs |