본문 바로가기
알고리즘 문제풀이/백준

[백준 14588] Line Friends (Small)

by m2162003 2021. 1. 2.

www.acmicpc.net/problem/14588

 

14588번: Line Friends (Small)

Q개의 줄에 걸쳐 두 선분이 가까운 정도를 출력한다. 만약, 두 선분 사이의 친구 관계가 단절되었다면 -1을 출력한다.

www.acmicpc.net

#include <stdio.h>
#include <algorithm>
#include <vector>
#define MAX 1e9

using namespace std;
struct s
{
  int left, right;
};

int n, l, r, q, a, b;
s arr[301];
int dis[301][301];

bool check(int a, int b)
{
  if (arr[a].right < arr[b].left || arr[b].right < arr[a].left)
  {
    return 0;
  }
  return 1;
}
int main(void)
{
  fill(&dis[0][0], &dis[300][301], MAX);
  scanf("%d", &n);

  for (int i = 1; i <= n; i++)
  {
    scanf("%d%d", &l, &r);
    arr[i] = {l, r};
    dis[i][i] = 0;
  }

  for (int i = 1; i < n; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      if (i == j)
        continue;
      if (check(i, j))
      {
        dis[i][j] = dis[j][i] = 1;
      }
    }
  }

  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      for (int k = 1; k <= n; k++)
      {
        dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
      }
    }
  }

  scanf("%d", &q);
  vector<int> res;
  while (q--)
  {
    scanf("%d%d", &a, &b);
    if (dis[a][b] == MAX)
    {
      res.push_back(-1);
    }
    else
    {
      res.push_back(dis[a][b]);
    }
  }

  for (auto a : res)
  {
    printf("%d\n", a);
  }

  return 0;
}

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1037] 약수  (0) 2021.01.03
[백준 1026] 보물  (0) 2021.01.03
[백준 2015] 수들의 합 4  (0) 2021.01.01
[백준 6118] 숨바꼭질  (0) 2021.01.01
[백준 2262] 토너먼트 만들기  (0) 2020.12.31

댓글