백준 14588 - Line Friends (Small)

www.acmicpc.net/problem/14588

 

각 선분의 친분 정도를 구해야 하는 문제이다.

 

친구는 1, 친구의 친구는 2, 친구의 친구의 친구는 3과 같이 친분이 정의되므로 각 선분의 친분 정도는 서로 얼마나 빠르게 다가갈 수 있는지, 즉 각 선분간의 최단 경로를 구해야 하는 것으로 풀이할 수 있다.

 

우선 이중 for문을 통해 친분의 정도가 1인 선분의 짝을 탐색하여 그 연결을 인접행렬로 구현한다.

 

그 후 플로이드 워셜을 수행하여 각 선분 사이의 최단 경로를 찾는다.

 

그 후 질의에 따라 친분의 정도, 혹은 친구가 아닌지를 출력하면 시간 내에 AC를 받을 수 있다.

 

전체코드

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int dp[300][300];

int main()
{
    fill(&dp[0][0], &dp[0][0] + 300 * 300, 1e9);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    
    vector<pair<int, int>> line(n);
    
    for (int i = 0; i < n; ++i)
    {
        int l, r;
        cin >> l >> r;
        line[i] = {l, r};
        dp[i][i] = 0;
    }
    
    for (int j = 0; j < n; ++j)
        for (int k = 0; k < n; ++k)
            if (j != k && ((line[j].first <= line[k].first && line[j].second >= line[k].first) || (line[j].first <= line[k].second && line[j].second >= line[k].second)))
                dp[j][k] = dp[k][j] = 1;
    
    for (int c = 0; c < n; ++c)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                dp[i][j] = min(dp[i][j], dp[i][c] + dp[c][j]);
    
    int qry; cin >> qry;
    
    while (qry--)
    {
        int a, b;
        cin >> a >> b;
        
        if (dp[a - 1][b - 1] != 1e9)
            cout << dp[a - 1][b - 1] << '\n';
        else
            cout << "-1\n";
    }
}