문제
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호가 주어진다.
출력
첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.
예전에 막 짠 코드를 수정해 다시 짠 것. 다익스트라 알고리즘으로 풀었다.
다만 과정에서 중복된 연산을 여러 번 진행한 부분이 있다.
(result1, result2를 계산하는 부분에서 getDistance(1, mid1) 과 (1,mid2)는 함수를 한 번만 돌려서 모두 얻어낼 수 있고,
(mid2, n) 과 (mid1, n)또한 마찬가지. (mid1, mid2)와 (mid2, mid1)또한 같은 값인데 여러 번 불러낸 것이 된다.)
이 문제는 함수를 계속 부르는 것이 비효율이지만, 직관적으로는 이렇게 짜는 게 나을 것 같았다.
결과는 메모리 16M정도를 사용하여 330ms정도에 결과가 나왔다.
LENGTH_MAX는 vertex갯수인 800과, 한 edge의 최댓값인 1000을 곱한 것이 거리의 최댓값이므로 800000을 최대로, 중간점이 2개이므로, 2400000을 MAX로 설정하였다. 물론 이 수가 작아서 충분히 크게 설정한 것이고, 실제로는 이 값보다 작은 값이 실제 최댓값으로 나오게 된다.
#include<iostream>
#include<queue>
#include<map>
const int LENGTH_MAX = 2400010;
using namespace std;
map<int, int> edge[800]; // adjacency list
int n, e;
int getDistance(int from, int to) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // save distance(result) in order of <distance, vertex>
int dist[800];
bool done[800];
for (int i = 0; i < n; i++) {
dist[i] = LENGTH_MAX;
done[i] = false;
}
dist[from - 1] = 0;
q.push(make_pair(0, from - 1));
while (!q.empty()) {
int cur_vert = q.top().second;
int cur_dist = q.top().first;
q.pop();
if (done[cur_vert]) continue;
done[cur_vert] = true;
for (pair<const int, int> temp : edge[cur_vert]) { // temp.first : vertex index , temp.second : edge length
if (temp.second + cur_dist < dist[temp.first]) {
dist[temp.first] = temp.second + cur_dist;
q.push(make_pair(dist[temp.first], temp.first));
}
}
}
return dist[to - 1];
}
int main() {
int from, to, length, mid1, mid2;
cin >> n >> e;
for (int i = 0; i < e; i++) {
cin >> from >> to >> length;
if (edge[from - 1][to - 1] == 0 || length < edge[from - 1][to - 1]) {
edge[from - 1][to - 1] = length;
edge[to - 1][from - 1] = length;
}
}
cin >> mid1 >> mid2;
int result1 = getDistance(1, mid1) + getDistance(mid1, mid2) + getDistance(mid2, n);
int result2 = getDistance(1, mid2) + getDistance(mid2, mid1) + getDistance(mid1, n);
int result = result1 < result2 ? result1 : result2;
if (result >= LENGTH_MAX) {
cout << -1;
}
else {
cout << result;
}
return 0;
}새로 글을 쓰려다가 그냥 아래에 첨부하는 게 나을 것 같아 아래에 첨부.
필요없는 연산을 여러 번 하게 되는 코드여서 그 문제를 해결하기 위해 약간의 수정을 가했다.
원래의 코드를 대부분 재활용했으므로, 함수의 오버로딩에서 parameter가 바뀐 것, result1,2를 계산하는 부분 외에는 거의 같은 코드.
함수는 하나의 출발점에서 여러 목적지로 가는 거리를 재는 함수를 기본으로 구현했다.
목적지를 vector기반 으로 받는 것으로부터, array형으로 입력을 받거나, 하나의 목적지로 가는 것도 구현.
vector기반이어서 size를 사용하면 굳이 목적지의 갯수는 parameter로 받지 않아도 되지만, 입력값의 validity를 확인할 수 있을 것 같아 일단 받았다.
validity checking은 함수에 포함되어 있지 않다.
결과를 보니 메모리는 같은 양을 사용하고, 시간은 2/3로 줄었다.
어차피 함수를 부른 후에 메모리는 해제될 것이므로 메모리의 차이는 없는게 맞을 것이다.
연산 횟수에 있어서는, 기존엔 6번의 다익스트라 알고리즘을 수행하지만, 바꾼 코드에서는 3번만 수행하면 되기 때문에 이 정도 시간이 줄어든 것 같다.
아래는 수정한 코드.
#include<iostream>
#include<queue>
#include<map>
#include<vector>
const int LENGTH_MAX = 2400010;
using namespace std;
map<int, int> edge[800]; // adjacency list
int n, e;
vector<int> getDistance(int from, int numOfDestinations, vector<int> destinations) {
vector<int> result;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // save distance(result) in order of <distance, vertex>
int dist[800];
bool done[800];
for (int i = 0; i < n; i++) {
dist[i] = LENGTH_MAX;
done[i] = false;
}
dist[from - 1] = 0;
q.push(make_pair(0, from - 1));
while (!q.empty()) {
int cur_vert = q.top().second;
int cur_dist = q.top().first;
q.pop();
if (done[cur_vert]) continue;
done[cur_vert] = true;
for (pair<const int, int> temp : edge[cur_vert]) { // temp.first : vertex index , temp.second : edge length
if (temp.second + cur_dist < dist[temp.first]) {
dist[temp.first] = temp.second + cur_dist;
q.push(make_pair(dist[temp.first], temp.first));
}
}
}
for (int i = 0; i < numOfDestinations; i++) {
result.push_back(dist[destinations[i] - 1]);
}
return result;
}
int getDistance(int from, int to) {
vector<int> destinations = { to };
return getDistance(from, 1, destinations)[0];
}
vector<int> getDistance(int from, int numOfDestinations, int destinations[]) {
vector<int> des_vec;
for (int i = 0; i < numOfDestinations; i++) {
des_vec.push_back(destinations[i]);
}
return getDistance(from, numOfDestinations, des_vec);
}
int main() {
int from, to, length, mid1, mid2;
cin >> n >> e;
for (int i = 0; i < e; i++) {
cin >> from >> to >> length;
if (edge[from - 1][to - 1] == 0 || length < edge[from - 1][to - 1]) {
edge[from - 1][to - 1] = length;
edge[to - 1][from - 1] = length;
}
}
cin >> mid1 >> mid2;
int result1, result2;
//result1 = getDistance(1, mid1) + getDistance(mid1, mid2) + getDistance(mid2, n);
//result2 = getDistance(1, mid2) + getDistance(mid2, mid1) + getDistance(mid1, n);
vector<int> from1 = getDistance(1, 2, { mid1, mid2 }), fromN = getDistance(n, 2, { mid1, mid2 });
int mid1Tomid2 = getDistance(mid1, mid2);
result1 = from1[0] + mid1Tomid2 + fromN[1];
result2 = from1[1] + mid1Tomid2 + fromN[0];
int result = result1 < result2 ? result1 : result2;
if (result >= LENGTH_MAX) {
cout << -1;
}
else {
cout << result;
}
return 0;
}
'Exercises > 길찾기' 카테고리의 다른 글
| 백준 1504 (1) | 2018.05.06 |
|---|---|
| 1504 cpp (0) | 2018.05.05 |
| 백준 1504 수정 (0) | 2018.05.05 |
| 백준 1504 (2) | 2018.05.04 |
| 백준 문제 1504 (0) | 2018.05.03 |