백준 14588 Line Friends(small)

작성일 | In |

Problem : Line Friends(small)

유형 : 플로이드 워셜

문제 해석

  • 선분들끼리 얼마나 가까운 관계인지를 확인하라

문제 재해석

  • 친구 관계 이므로 양방향 이다.
  • 친구 관계가 이어지지 않는다면 -1을 출력한다.

해결 전략

  • 플로이드 워셜을 이용하여 각 친구들간의 관계를 구한다.

주의할점

  • 한쪽이 일방적으로 아는 관계가 아니다.

설계, 구현

  • 선분의 길이를 전부 비교하며 친구 관계를 만든다.
    • A 선분과 B 선분을 비교할때, 둘이 겹치는 구간이 있으면, 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
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

const int INF = 1000;
int n;
int cost[302][302];
vector<pii> lines;

void Floyd() {
    for (int visit = 1; visit <= n; ++visit) {
        for (int s = 1; s <= n; ++s) {
            for (int e = 1; e <= n; ++e) {
                cost[s][e] = min(cost[s][e], cost[s][visit] + cost[visit][e]);
                cost[e][s] = cost[s][e];
            }
        }
    }
}

void Solve() {

    Floyd();

    int q;
    cin >> q;
    int line_1, line_2;
    while (q--) {
        cin >> line_1 >> line_2;
        if (cost[line_1][line_2] == INF) cout << -1 << "\n";
        else cout << cost[line_1][line_2] << "\n";
    }
}

void Connect_Check() {
    for (int i = 0; i < n; ++i) {
        int s = lines[i].first;
        int e = lines[i].second;

        for (int ii = i + 1; ii < n; ++ii) {
            int qs = lines[ii].first;
            int qe = lines[ii].second;

            if (qs > e or qe < s) continue;
			cost[i + 1][ii + 1] = 1;
			cost[ii + 1][i + 1] = 1;
        }
    }
}

void Init() {
    for (int i = 1; i <= n; ++i) {
        for (int ii = 1; ii <= n; ++ii) {
            if (i == ii) continue;
            cost[i][ii] = INF;
        }
    }
}

void Input() {
    cin >> n;
    Init();

    lines.resize(n);
    for (auto& line : lines) {
        cin >> line.first >> line.second;
    }
    Connect_Check();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

디버깅

  • 양방향 간선 인걸 놓쳤었다.
  • cost를 1부터 넣어야하는데, 0부터 넣는 실수를 했다.

피드백

  • 1 부터 시작인지 0 부터 시작인지 잘 구별하자.