[백준 14588] Line Friends (Small) (C#, C++) - soo:bak

문제 링크

14588번 - Line Friends (Small)

설명

수직선 위에 여러 선분이 있을 때, 서로 겹치는 선분끼리 친구가 됩니다. 두 선분 사이의 최소 친구 단계를 구하는 문제입니다.

접근법

두 선분이 한 점이라도 공유하면 직접 친구가 됩니다. 이 관계를 그래프로 나타내면, 직접 친구 사이는 거리가 1인 간선으로 연결됩니다.

선분의 개수가 적으므로 모든 선분 쌍에 대해 겹치는지 확인하고, 겹치면 거리를 1로 설정합니다. 그 후 플로이드 워셜 알고리듬으로 모든 쌍의 최단 거리를 구합니다.

각 질의에 대해 두 선분 사이의 최단 거리를 출력하고, 연결되어 있지 않으면 -1을 출력합니다.

---

Code

C#

using System;

class Program {
  const int INF = 1_000_000_000;

  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var seg = new (int l, int r)[n];
    for (var i = 0; i < n; i++) {
      var parts = Console.ReadLine()!.Split();
      seg[i] = (int.Parse(parts[0]), int.Parse(parts[1]));
    }

    var dist = new int[n, n];
    for (var i = 0; i < n; i++)
      for (var j = 0; j < n; j++)
        dist[i, j] = (i == j) ? 0 : INF;

    for (var i = 0; i < n; i++) {
      for (var j = i + 1; j < n; j++) {
        var overlap = !(seg[i].r < seg[j].l || seg[j].r < seg[i].l);
        if (overlap) {
          dist[i, j] = 1;
          dist[j, i] = 1;
        }
      }
    }

    for (var k = 0; k < n; k++)
      for (var i = 0; i < n; i++)
        for (var j = 0; j < n; j++) {
          var cand = dist[i, k] + dist[k, j];
          if (cand < dist[i, j]) dist[i, j] = cand;
        }

    var q = int.Parse(Console.ReadLine()!);
    while (q-- > 0) {
      var parts = Console.ReadLine()!.Split();
      var a = int.Parse(parts[0]) - 1;
      var b = int.Parse(parts[1]) - 1;
      var ans = dist[a, b];
      Console.WriteLine(ans >= INF ? -1 : ans);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  const int INF = 1e9;
  int n; cin >> n;
  vector<pii> seg(n);
  for (auto& p : seg) cin >> p.first >> p.second;

  vvi dist(n, vi(n, INF));
  for (int i = 0; i < n; i++) dist[i][i] = 0;

  auto overlap = [&](int i, int j) {
    return !(seg[i].second < seg[j].first || seg[j].second < seg[i].first);
  };

  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
      if (overlap(i, j))
        dist[i][j] = 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;
  while (q--) {
    int a, b; cin >> a >> b;
    --a; --b;
    cout << (dist[a][b] >= INF ? -1 : dist[a][b]) << "\n";
  }

  return 0;
}