https://www.acmicpc.net/problem/14588


어떠한 선분과 선분의 관계를

2차원 배열로 만들어서 표현할 수 있겠다고 생각했습니다.


그래서 우선 거리가 1인 친구 즉 맞닿아 있는 친구를 테이블로 작성하고

그 후에 플로이드를 통해서 모든 관계에서의 최단 거리를 구했습니다.


코드입니다.

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 <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
 
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
int dist[300][300];
vector<pii> v;
 
bool f(int a, int b) {
    if (v[a].second < v[b].first || v[b].second < v[a].first) return 0;
    return 1;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back(mp(a, b));
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            else dist[i][j] = INF;
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (f(i, j)) {
                dist[i][j] = 1;
                dist[j][i] = 1;
            }
        }
    }
 
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
 
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        cout << (dist[a][b] == INF ? -1 : dist[a][b]) << '\n';
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 최단 거리' 카테고리의 다른 글

[1686] 복날  (0) 2017.07.12
[1507] 궁금한 민호  (0) 2017.07.08

https://www.acmicpc.net/problem/1686


흠흠...

사실 최단 거리라기 보다는.. 가장 비용을 적게 들여서(가장 벙커를 적게 방문하면서) 목적지로 도달하는 문제입니다.


처음에 접근은 이분탐색으로 했습니다.

벙커들을 sort하여 갈 수 있는 시간내로 이동할 수 있는 최대 거리로 이동을 하여서 목적지에 도달하게 했습니다.


이 문제에서 이분탐색을 쓰면 생기는 오류는 방향입니다.

x, y 좌표가 있기 때문에 방향이 있어서 최대한의 거리가 절대값이기 때문에 오류가 발생합니다.


그래서 dfs로 해결하려 했으나 dfs는 최적의 해를 보장해주지 않기 때문에 완전 탐색을 해야만합니다.

시간초과로 실패했습니다.


해결 방법은 bfs 혹은 다익스트라로 해결하시면 됩니다.

사실 해보니깐.. 다익스트라는 딱히 필요없는듯.. 어차피 bfs는 최적을 보장하기 때문에.......


풀 코드입니당.

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
#include <cstdio>
#include <queue>
 
using namespace std;
 
#define mp make_pair
#define ll long long
 
vector<pair<double, double> > b;
bool visit[1005];
int v, m;
double xs, ys;
double xt, yt;
 
double distance(pair<double, double> a, pair<double, double> b) {
    double x = a.first - b.first;
    double y = a.second - b.second;
    return x*x + y*y;
}
 
int main() {
    scanf("%d %d", &v, &m);
    scanf("%lf %lf", &xs, &ys);
    scanf("%lf %lf", &xt, &yt);
 
    double ttx, tty;
    while (~scanf("%lf%lf", &ttx, &tty)) {
        b.push_back(mp(ttx, tty));
    }
    b.push_back(mp(xt, yt)); //도착점 삽입
 
    queue<pair<int, pair<double, double> > > q;
    q.push(mp(0, mp(xs, ys)));
    
    ll md = v * m * 60; // 이동할 수 있는 최대거리
    md *= md; // 최대거리의 제곱
 
    while (!q.empty()) {
        int cnt = -q.front().first;
        double x = q.front().second.first;
        double y = q.front().second.second;
        q.pop();
 
        if (x == xt && y == yt) {
            printf("Yes, visiting %d other holes.\n", cnt - 1);
            return 0;
        }
 
        for (int i = 0; i < b.size(); i++) {
            if (visit[i] || distance(mp(x, y), b[i]) > md) continue;
            visit[i] = 1;
            q.push(mp(-(cnt + 1), b[i]));
        }
    }
 
    puts("No.");
 
    return 0;
}
cs


저작자표시

'알고리즘 > 최단 거리' 카테고리의 다른 글

[14588] Line Friends(small)  (0) 2017.07.23
[1507] 궁금한 민호  (0) 2017.07.08

https://www.acmicpc.net/problem/1507



별 이상한 방법으로 엄청 시도했습니다..

dfs, bfs, 비트마스크 등등 ㅠㅠㅠㅠ....


해결 알고리즘은 플로이드-와샬을 이용하는 것입니다.


플로이드-와샬을 이용하면 모든 정점에 대한 최단거리를 테이블로 만들 수 있습니다.

잘모르시는 분들은 다른 블로그나 책을 통해서 공부하시고 참고해주시기 바랍니다.


input으로 들어오는 테이블이 현재 최단 거리 테이블이니

그 테이블을 기준으로 다시 한번 플로이드를 돌립니다.


이 때 중요한 것은

i - k - j(i에서 k를 거쳐 j로 가는 거리)가 i - j와 같다면

i - j간선, i - k간선, k-j간선 총 세개가 필요했던 것이

i - k, k - j 두 개의 간선으로 표현이 가능합니다.


플로이드를 통해서 이러한 간선을 전부 체크해준 후에

마지막에 체크되지 않은 간선 / 2 혹은 2차원 테이블에서 반만 더해준 후에 결과를 출력합니다.


-1이 출력되는 조건은 input으로 들어온 데이터가 최단거리가 아닐 때 입니다.


아래는 풀 코드입니다.


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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 200
#define mp make_pair
#define pii pair<int, int>
using namespace std;
 
int spend[20][20];
int n;
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> spend[i][j];
        }
    }
 
    bool destroy[20][20] = { 0, };
    //플로이드
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || i == k || k == j) continue;
                
                //삭제할 간선 찾기
                if (spend[i][j] == spend[i][k] + spend[k][j]) {
                    destroy[i][j] = 1;
                }
                //i, j가 최단거리가 아닐경우 -1 출력
                else if (spend[i][j] > spend[i][k] + spend[k][j]) {
                    puts("-1");
                    return 0;
                }
            }
        }
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            ret += !destroy[i][j] * spend[i][j];
        }
    }
 
    cout << ret;
 
    return 0;
}
cs


'알고리즘 > 최단 거리' 카테고리의 다른 글

[14588] Line Friends(small)  (0) 2017.07.23
[1686] 복날  (0) 2017.07.12

+ Recent posts

티스토리툴바