2021. 2. 22. 18:19ㆍ알고리즘/알고리즘 문제 [hard]
1. 문제
새로 건설할 당위성이 있다:
고속도로를 통해 오갈 수 없던 두 도시가 새로 연결됨.
두 도시를 오가는 데 걸리는 시간이 단축 되어야함
N년간 하나씩 고속도로를 건설할때
이들 중 몇 개가 의미가 없는지 계산하여라
2. 플로이드 n번
역시 간단한 풀이는 그냥 건설할때마다 플로이드를 수행하는 것이다,
하지만 이는 시간초과로 문제를 시간안에 해결할 수 없다.
또다른 방법은 플로이드를 계산할때 a, b 정점을 경유하는지 기록하는 것
만약 고속도로가 추가되면 이 기록을따라 a->b, b->a거리를 업데이트 시키고,
b와 a에 대해서만 플로이드를 다시 수행하는 것이다.
하지만 이것은 구현도 까다롭고 복잡하다.
|
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#include <algorithm>
#include <vector>
#include <iostream>
#include <utility>
using namespace std;
const int INF = 123456789;
int C;
int V;
int M;
int N;
vector<vector<int> > adj;
vector<vector<int> > graph;
void floyd()
{
for(int i = 0; i < V; i++)
for(int j = 0; j < V; j++)
if(i == j)
adj[i][i] = 0;
else
adj[i][j] = graph[i][j];
for(int k = 0; k < V; k++)
{
for(int i = 0; i < V; i++)
{
for(int j = 0; j < V; j++)
{
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}
}
}
}
int add(int a, int b, int c)
{
if(adj[a][b] > c || adj[b][a] > c)
{
graph[a][b] = c;
graph[b][a] = c;
floyd();
return 0;
}
return 1;
}
int main()
{
cin>>C;
while(C--)
{
int ret = 0;
cin>>V>>M>>N;
adj = vector<vector<int> > (V, vector<int>(V, INF));
graph = vector<vector<int> > (V, vector<int>(V, INF));
for(int i = 0; i < M; i++)
{
int a, b, c;
cin>>a>>b>>c;
c = min(c, graph[a][b]);
graph[a][b] = c;
graph[b][a] = c;
}
floyd();
for(int i = 0 ; i < N; i++)
{
int a, b, c;
cin>>a>>b>>c;
ret += add(a, b, c);
}
cout<<ret<<"\n";
}
}
|
cs |
3. 책의 풀이: 최단 거리의 갱신
그래프에 대해 플로이드 알고리즘을 한 번 수행해서 최단 거리 행렬 adj를 먼저 얻어낸다.
그 후 그래프에 새 간선이 추가되었을 때 adj를 적절히 갱신해야한다.
위에서 a-b의 간선이 주어졌을때 a와 b에서만 플로이드를 적용시키면된다에서 더 나아가
책에서는 adj[i][a] + c + adj[b][j] / adj[i][b] + c + adj[a][j] / adj[i][j] 에서 가장 작은것으로 adj[i][j]를 업데이트 시켰다.
a 와 b가 끝점이나 시작점인것에 c 를 더한것이 adj[i][j]의 값으로 업데이트된다는 것은
이 경로가 추가된 a-b b-a 로 인해 더 작은 시간을 소모하게된것을 의미하고, 연결되지 않았으면 연결한다는 것이다.
이것은 플로이드 알고리즘의 동작원리를 이용한것이며
경유할 수 있는 정점의 목록을 늘려가는 대신 경유할 수 있는 간선의 목록을 늘려가는것으로 변형시킨것이다.
이러한 변형은 유도과정을 생각해보면 알고리즘의 정당성을 해치지 않는다.
간선의 집합 e를 경유할 수 있을 때 u에서 v로 가는 최단 거리를 De(u, v)라고하자
이때 e의 원소 중 간선 (a, b)가 있다고하고 e-{(a-b)} = e' 라고 쓰면
De = min{ De'(u, v),
De'(u, a) + w(a, b) + De'(b, v),
De'(u, b) + w(a, b) + De'(a, v)}
가 성립한다.
간선을 어느 방향으로 타고 갈 것인가를 정해야하기 때문에 경우의 수 가 3개가 됨을 알 수 있다.
|
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#include <algorithm>
#include <vector>
#include <iostream>
#include <utility>
using namespace std;
const int INF = 123456789;
int C;
int V;
int M;
int N;
vector<vector<int> > adj;
vector<vector<int> > graph;
void floyd()
{
for(int i = 0; i < V; i++)
for(int j = 0; j < V; j++)
if(i == j)
adj[i][i] = 0;
else
adj[i][j] = graph[i][j];
for(int k = 0; k < V; k++)
{
for(int i = 0; i < V; i++)
{
for(int j = 0; j < V; j++)
{
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}
}
}
}
int add(int a, int b, int c)
{
if(adj[a][b] > c || adj[b][a] > c)
{
for(int i = 0; i < V; i++)
for(int j = 0; j < V; j++)
adj[i][j] = min(adj[i][j], min(adj[i][a] + c + adj[b][j], adj[i][b] + c + adj[a][j]));
return 0;
}
return 1;
}
int main()
{
cin>>C;
while(C--)
{
int ret = 0;
cin>>V>>M>>N;
adj = vector<vector<int> > (V, vector<int>(V, INF));
graph = vector<vector<int> > (V, vector<int>(V, INF));
for(int i = 0; i < M; i++)
{
int a, b, c;
cin>>a>>b>>c;
c = min(c, graph[a][b]);
graph[a][b] = c;
graph[b][a] = c;
}
floyd();
for(int i = 0 ; i < N; i++)
{
int a, b, c;
cin>>a>>b>>c;
ret += add(a, b, c);
}
cout<<ret<<"\n";
}
}
|
cs |
- 알고리즘 문제해결전략 965p
'알고리즘 > 알고리즘 문제 [hard]' 카테고리의 다른 글
| [그래프][시도x] NTHLON 철인 N종 경기 (0) | 2021.02.24 |
|---|---|
| [그래프] [시도x] TPATH 여행 경로 정하기 (0) | 2021.02.23 |
| [그래프][시도x] CHILDRENDAY 어린이날 (0) | 2021.02.16 |
| [그래프] [2-SAT] [시도 x] MEETINGROOM 회의실 배정 (0) | 2021.02.15 |
| [그래프] [시도x] WORDCHAIN 단어 제한 끝말잇기 (0) | 2021.02.13 |