[백준 / BOJ] C++ 9373 복도 뚫기

9373번: 복도 뚫기

 

문제

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

9373번: 복도 뚫기

 

 

풀이

센서에 감지되지 않고 복도를 지나가기 위해서는 각 센서의 감지 범위 바깥으로 지나가야 하고 벽을 벗어날 수도 없다. 우리가 구하고자 하는 것은 끝까지 통과할 수 있는 가장 긴 길이이다. 즉, 작은 간격부터 탐색하다가 특정 조건에서 답이 구해지는 것이다.

 

풀이에 사용된 방법은 최소 스패닝 트리(MST) 알고리즘이다. 크루스칼(Kruskal) 알고리즘을 사용한 방법으로 문제를 풀었다. 먼저 풀이의 가장 큰 전제는 두 벽이 한 컴포넌트가 되면, 그때 연결된 간선의 가중치(거리)가 답이 된다.

 

그 이유에 대해 알아보자. 아주 많은 원들이 있다고 가정해보자. 그리고 그 원들 사이를 잇는 수많은 간선이 있을 것이다. 이때 두 벽이 한 컴포넌트가 된다는 것은 반드시 지나가야 하는 구간이 이어졌다는 것이고, 크루스칼 알고리즘의 특성상 거리가 짧은 간선부터 이어 주기 때문에 이후의 간선들은 반드시 지나가야 하는 구간보다 길이가 클 수밖에 없다. 즉, 반드시 지나가야 하는 구간만 통과할 수 있다면 다른 나머지 구간의 길이는 신경 쓸 필요가 없어진다.

 

 

 

 

 

원의 수 N과 두 벽 사이의 간격 w를 입력받는다. 양쪽의 벽을 하나의 정점으로 보기 때문에 N+2개의 정점이 필요하다. 따라서 N+1크기의 배열을 선언해 주고 0~N-1번 인덱스는 각 원의 정점, N번과 N+1번 인덱스는 x=0인 벽과 x=w인 벽이다. 이때, 센서가 없을 가능성에 대비해 두 벽을 잇는 간선도 추가해 준다.

 

각 원(센서)의 좌표와 반지름을 입력받을 때마다 원과 두 벽 사이의 거리에 따라 연산을 진행해 준다. 벽과의 거리가 양수이면 간선을 추가해 주고 이외의 경우에는 벽과 union 해주어 한 컴포넌트로 만들어준다. 그리고 각 원에 대해서도 다른 모든 원들과의 거리를 구해 양수인 경우 간선을 추가해 주고 이외의 경우 두 원을 union 해준다.

 

이제 크루스칼 알고리즘에 따라 최소 스패닝 트리를 구성해 가면서 간선을 이어줄 때마다 두 벽이 한 컴포넌트로 이어졌는지 확인하고 만약 이어졌을 경우 제일 최근 이어준 간선의 (길이 / 2)가 정답이 된다.

 

 

주석을 보며 코드를 읽어보는게 더 이해가 쉬울 수도 있다. 아래는 이해를 돕기 위한 그림이다. (도움이 될지 모르겠다..)

하늘색과 연두색은 각각 처음 시작부터 이어진 각각의 컴포넌트고 빨간선은 간선, 초록색은 크루스칼 알고리즘에 이어지는 간선이다. 파란색은 각 벽과의 거리를 나타낸다.

 

 

코드

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

vector<int> p;

int find(int x) {
  if (p[x] != x)
    p[x] = find(p[x]);
  return p[x];
}

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if (x < y)
    p[y] = x;
  else
    p[x] = y;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    int w, n;
    vector<pair<double, pair<int, int>>> edge;
    vector<tuple<int, int, int>> pos; // r, x, y 저장
    cin >> w >> n;
    edge.push_back({w, {n, n + 1}}); // 두 벽을 간선으로 이어준다
    p.resize(n + 2);
    iota(p.begin(), p.end(), 0);
    for (int i = 0; i < n; i++) {
      int x, y, r;
      cin >> x >> y >> r;
      pos.push_back({r, x, y}); // 정보 저장
      if (x - r > 0) // x=0과의 거리가 양수라면
        edge.push_back({x - r, {i, n}}); // 간선 추가
      else // 아니면
        merge(i, n); // 같은 컴포넌트로 유니온
      if (w - x - r > 0) // x=w와의 거리가 양수라면
        edge.push_back({w - x - r, {i, n + 1}}); // 간선 추가
      else // 아니면
        merge(i, n + 1); // 같은 컴포넌트로 유니온
    }
    // 모든 원에 대해
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        auto [r1, x1, y1] = pos[i];
        auto [r2, x2, y2] = pos[j];
        // 거리 d = 두 원의 중점 사이의 거리 - 각 원의 반지름
        double d = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2)) - r1 - r2;
        if (d > 0) // 거리가 양수라면
          edge.push_back({d, {i, j}}); // 간선 추가
        else // 아니면
          merge(i, j); // 같은 컴포넌트로 유니온
      }
    sort(edge.begin(), edge.end()); // 간선 거리 기준으로 정렬
    double ans = 0; // 기본 정답 0
    // 크루스칼 알고리즘
    for (auto [weight, path] : edge)
      // 두 정점이 같은 컴포넌트가 아니라면
      if (find(path.first) != find(path.second)) {
        merge(path.first, path.second); // 유니온
        // x=0과 x=w가 같은 컴포넌트가 되면
        if (find(n) == find(n + 1)) {
          ans = weight / 2; // 이 때의 거리가 최댓값
          break;
        }
      }
    cout.precision(9); // 소숫점 9번째 자리까지 출력
    cout << fixed << ans << '\n';
  }
  return 0;
}