문제 URL : https://www.acmicpc.net/problem/12930
12930번: 두 가중치
0번 정점에서 1번 정점으로 가는 최단 경로의 비용을 출력한다. 0번에서 1번으로 갈 수 없는 경우에는 -1을 출력한다.
www.acmicpc.net
문제 접근법 :
w1과 w2를 곱해서 더한결과가 낮은 순으로 다익스트라를 이용하여 푸는 문제이지만 굉장히 어려웠던 문제입니다.
수십번을 틀리고 다익스트라를 이용하긴해도 제가 풀었을땐 다익스트라로 나올수있는 경우의 수를 모두구해서 나온결과였고 시간은 매우 느립니다. 하지만 풀고난후 다른 사람풀이도 참조하여 시간을 줄이는 방법을 배울수있어 굉장히 좋은 문제입니다. 우선 제가 풀었던 코드와 참조해서 수정한 코드 두개다 올릴게요
소스코드 :
첫번째 :
|
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
|
//By콩순이냉장고
#include <iostream>
#include <string>
#include <vector>
#include<algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
int w[2][20][20];
int dist[20];
int n;
vector<int> v[20];
void input() {
cin >> n;
char c;
for (int k = 0; k < 2; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> c;
if (c == '.')
continue;
w[k][i][j] = c - '0';
v[i].push_back(j);
v[j].push_back(i);
}
}
}
}
struct point {
int cur, sumcost, w1, w2;
set<int> s;
friend bool operator<(const point& p1, const point& p2) {
return p1.sumcost > p2.sumcost;
}
};
int dijkstrak() {
fill(dist, dist + n, 1e8);
dist[0] = 0;
priority_queue<point> pq;
set<int> temps;
temps.insert(0);
pq.push({ 0,0,0,0,temps });
while (!pq.empty()) {
int cur = pq.top().cur;
int sumcost = pq.top().sumcost;
int w1 = pq.top().w1;
int w2 = pq.top().w2;
set<int> s=pq.top().s;
pq.pop();
for (int next : v[cur]) {
int nw1 = w1 + w[0][cur][next];
int nw2 = w2 + w[1][cur][next];
int cost = nw1 * nw2;
if (dist[next] > cost) {
s.insert(next);
pq.push({ next,cost,nw1,nw2 ,s});
dist[next] = cost;
}
else if (s.count(next)==0) {
s.insert(next);
pq.push({ next,cost,nw1,nw2 ,s});
}
}
}
return dist[1] == 1e8 ? -1 : dist[1];
}
void solve() {
cout << dijkstrak() << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
첫번째는 set을 이용해서 모든 경우의수를 다구했던코드이기에 느립니다.
두번째 :
|
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
|
//By콩순이냉장고
#include <iostream>
#include <string>
#include <vector>
#include<algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
int w[2][20][20];
int dist[20][300];
int n;
vector<int> v[20];
void input() {
cin >> n;
char c;
for (int k = 0; k < 2; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> c;
if (c == '.')
continue;
w[k][i][j] = c - '0';
if (j > i) {
v[i].push_back(j);
v[j].push_back(i);
}
}
}
}
}
struct point {
int cur, sumcost, w1, w2;
friend bool operator<(const point& p1, const point& p2) {
return p1.sumcost > p2.sumcost;
}
};
int dijkstrak() {
for (int i = 1; i < n; i++)
fill(dist[i], dist[i] + 300, 1e8);
priority_queue<point> pq;
pq.push({ 0,0,0,0 });
while (!pq.empty()) {
int cur = pq.top().cur;
int sumcost = pq.top().sumcost;
int w1 = pq.top().w1;
int w2 = pq.top().w2;
pq.pop();
for (int next : v[cur]) {
int nw1 = w1 + w[0][cur][next];
int nw2 = w2 + w[1][cur][next];
int cost = nw1 * nw2;
if (dist[next][nw1] > cost) {
dist[next][nw1] = cost;
pq.push({ next,cost,nw1,nw2 });
}
else if (dist[next][nw2] > cost) {
dist[next][nw2] = cost;
pq.push({ next,cost,nw1,nw2 });
}
}
}
int res = 1e8;
for (int i = 0; i < 300; i++)
res = min(res, dist[1][i]);
return res == 1e8 ? -1 : res;
}
void solve() {
cout << dijkstrak() << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
두번째 코드는 나올수있는 w1과 w2에 대한 결과값을 배열로 저장하여 그가중치의 값에대해 가장 작은값을 저장하기에 굉장히 빠릅니다. 저는 이런 방법을 생각 못했고 덕분에 배울수있어 좋았습니다.
그치만 의문인게 n값이 커저도 20밖에 안되고 w를 다더해도 가질수있는값이 최대 180밖에 안되는것같은데
배열값을 200으로 잡으면 충분할 거라 생각했는데 인덱스 초과가 나오더군요
300으로 잡으니 다행이 초과가 나오지 않던데 왜그런건지 이해를 하질 못했습니다. 왜그런건지 아시는분 있다면 댓글을 남겨주시면 감사하겠습니다.
지적이나 조언 어떤 궁금증이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 16973 직사각형 탈출 (0) | 2021.06.23 |
|---|---|
| 백준 2559 수열 (0) | 2021.06.19 |
| 백준 1080 행렬 (0) | 2021.06.17 |
| 백준 16958 텔레포트 (0) | 2021.06.17 |
| 백준 2966 찍기 (0) | 2021.06.17 |