[종만북] 문제: FORTRESS

게시 2025/02/09 업데이트 2025/02/11

By 정승우

12 분읽는 시간

문제

$n (1 \leq n \leq 100)$개의 원형 장벽이 주어질 때, 최대 성벽을 몇 번이나 넘어야 하는지 구하시오.

맨 처음 큰 장벽이 주어지고, 나머지 $n-1$개의 장벽은 첫 장벽 안에 포함된다.

장벽은 서로 겹치고, 닿지 않는다.

문제 링크

서론

문제를 Tree Diameter Problem로 변환하고,

Tree Diameter Problem을 풀어봅시다.

아이디어

문제만 보면 어떻게 풀어야 할지 답이 안 보이나, 조건이 제한되어 있는게 핵심입니다.

원형 성벽이 겹치거나 닿지 않음.
맨 처음 외벽이 주어지고, 그 다음 성벽들은 외벽 안에 무조건 포함된다.

이 조건을 통해 모든 성벽 간의 관계는 포함 관계로 생각할 수 있으며,더 나아가서 이것이 트리 관계임을 생각할 수 있습니다.

따라서 트리의 지름 문제(Tree Diameter Problem)로 변환이 가능합니다.

성벽의 개수를 세는 문제이므로 Tree $T = (V, E)$에서 $E$의 $weight$를 $1$로 두고 풀면 될 듯 합니다.

트리의 지름 문제(Tree Diameter Problem)

트리의 지름이란, Tree $T = (V, E)$에서 두 노드 간의 최장 경로를 의미합니다.

따라서 이 문제란, 어떤 노트 두 개의 최장 경로를 구하는 문제입니다.

트리의 지름 문제를 푸는 법

트리의 지름 문제를 풀 때 크게 네 가지 방법이 있습니다.

임의의 시작점에서 DFS를 수행하여 가장 멀리 떨어진 노드 1를 찾고, 그 노드 1에서 DFS를 수행하여 가장 멀리 떨어진 노드 2를 찾음. 노드 1과 노드 2의 거리가 트리의 지름. (DFS 2번)
각 노드에 대해 자식 노드의 높이 중 가장 큰 값 best과 두 번째로 큰 값 secondBest를 구해서 현재 노드를 중심으로 한 경로의 길이는 best + secondBest이므로 이를 전역 변수에 갱신하여 트리의 지름을 구함. (DFS 한번 & 사실상 트리 동적 계획법)
트리의 모든 리프를 제거하며 트리의 중심을 찾은 뒤, 중심에서 최대 거리를 계산하는 법. (??)
All-Pairs Shortest Path 알고리즘 이용. ex) Floyd-warshall (대신 시간복잡도가 $O(n^2)$로 증가)

저는 트리를 구현할 때 vector<int> node[1...n]을 이용해 자식 노드만 edge로 연결하여 방향 비순환 그래프처럼 구현했기 때문에 2번 방법을 이용해 구현하였습니다.

트리를 구현할 때, 무방향 그래프처럼 구현해야 1번 방법을 이용할 수 있습니다.

무방향 그래프 구현이 어렵지 않은게, edge로 연결되는 노드에 자식 노드뿐만 아니라 부모 노드도 같이 넣어주면 됩니다. (대신 부모 노드를 처리하는 예외 코드가 있어야 합니다.)

1번 방법에 대한 정당성 증명

임의의 노드 $ x $에서 가장 먼 노드가 $ b $이므로, 어떤 노드 $ y $에 대해서도 $\mathrm{dist}(x, b) \ge \mathrm{dist}(x, y)$ 가 성립한다.

또한, $(p, q)$가 트리 지름의 양 끝이라고 할 때, $\mathrm{dist}(p, q) = D.$ 만약 $ b $가 지름 경로 $ p \to \cdots \to q $ 상에 존재하지 않는다면, 우리는 $(p, q)$보다 더 긴 경로를 구성할 수 있어야 하는데, 이는 $(p, q)$가 지름임에 모순된다.

(가정) $ b $가 지름 경로 $ p \to \cdots \to q $에 속하지 않는다고 하자.
트리이므로 $ p $와 $ b $를 잇는 유일한 단순 경로가 존재한다. 이를 $ p \to \cdots \to b $라 표현하겠다.
이제, $\mathrm{dist}(p, b)$는 0이 아니며 (서로 다른 노드라면), 만약 $\mathrm{dist}(p, q) = D$라면 삼각 부등식에 의해 $\mathrm{dist}(p, b) + \mathrm{dist}(b, q) \ge \mathrm{dist}(p, q) = D.$
특별한 경우: 만약 $ b $가 $ p \to q $ 경로 “밖”에 있다면, $ q $까지 연결하는 경로는 $ q \to p \to b $가 된다. 이때, $\mathrm{dist}(q, b) = \mathrm{dist}(q, p) + \mathrm{dist}(p, b) = D + \mathrm{dist}(p, b),$ 가 되어 $ D + \mathrm{dist}(p, b) $는 $ D $보다 큰 값을 갖는다. 즉, $\mathrm{dist}(q, b) > D.$ 이는 “$(p, q)$가 지름 경로라 $\mathrm{dist}(p, q) = D$가 최대”라는 가정에 정면 모순된다.
따라서, $ b $는 지름 경로 위에 놓이게 되며, “가장 먼 노드”라는 특성상 경로의 중간(내부)가 아니라 한쪽 끝(단말)에 위치하게 된다. (만약 중간에 있었다면, 더 먼 단말이 존재했을 것이기 때문이다.)

이로써,

”$ x $에서 BFS(또는 DFS)로 찾은 가장 먼 노드 $ b $는 트리 지름의 한 끝점이다.”

라는 사실이 증명된다.

2번 방법에 대한 증명

간략하게 설명하자면, 트리의 지름도 결국 어떤 노드를 분할점, 즉 루트를 가지게 됩니다.

선정한 노드에 대해서 노드의 child의 첫 번째, 두 번째로 긴 높이의 합이, 그 노드를 루트로 하는 최대 트리 지름임을 알 수 있습니다.

DFS/BFS를 활용하여 트리의 $n$개 노드에 대해서 재귀적으로 $diameter$값을 최댓값으로 갱신하며 지름을 찾는 알고리즘입니다

교과서에서는 이 방법을 이용하여 구현하였고,

제 풀이는 트리를 DAG로 생각하여 풀어서 2번 방법으로 구현하였습니다.

알고리즘 구상

알고리즘 설계

간략하게 설명하고 넘어가겠습니다.

Circle의 입력을 받아 반지름 기준 내림차순으로 정렬합니다. (모든 원은 포함 관계이므로 그리디한 접근을 이용)
각 Circle을 트리 구조로 만듭니다. (Circle A안에 Circle B가 포함될 수 있는지를 검사하며)
트리의 지름을 구하기 위해 2번 방법을 사용합니다. ($height$를 구하면서 전역 변수 $diameter$ 이용)
트리의 root에 대해 $height$를 구하는 연산 수행, 이후 $diameter$의 값 출력

알고리즘 구현

isContained()

Circle $a$안에 Circle $b$가 포함되는지 확인하는 bool 함수입니다.

  
bool isContained(int a, int b) {
    int dx = circle[a].x - circle[b].x;
    int dy = circle[a].y - circle[b].y;
    int dr = circle[a].r - circle[b].r;

    return dr > 0 && dx * dx + dy * dy <= dr * dr;
} // 원 a안에 b가 포함됨?

makeNode()

$node[i] = { \text{idx} \mid 1 \leq \text{idx} \leq n-1 }$에 대해 트리를 생성하는 makeNode() 함수입니다.

makeNode() 함수는 노드를 재귀적으로 호출하며, 포함 관계를 검사한 뒤 포함할 수 없는 경우 해당 노드에 엣지를 추가하는 방식으로 트리를 구성합니다.

  
void makeNode(int i, int idx) {
    for (int &edge : node[i]) {
        if (isContained(edge, idx)) {
            makeNode(edge, idx);
            return;
        }
    }
    node[i].push_back(idx);
}

height()

node $curr$의 높이를 구하는 함수이지만, 안에서 두 번째로 높은 자식 subTree의 height를 구하며 트리의 지름 diameter을 구합니다.

  
int height(int curr) {
    int best = 0, secondBest = 0, ret = 0;
    for (int next : node[curr]) {
        int h = height(next);
        if (h > best) {
            secondBest = best;
            best = h;
        } else if (h > secondBest) {
            secondBest = h;
        }
    }
    diameter = max(diameter, best + secondBest);
    return best + 1;
}

main()

위에서 작성된 함수를 이용하여 알고리즘을 구현합니다.

  
int main() {
    fastIO;
    int C;
    cin >> C;
    while (C--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> circle[i].x >> circle[i].y >> circle[i].r;
        }
        sort(circle, circle + n); // 반지름 내림차순 정렬
        for (int i = 0; i < n; i++) {
            node[i].clear();
        } // init()

        for (int i = 1; i < n; i++) {
            makeNode(0, i);
        } // node간의 연결 구현
        diameter = 0;
        height(0);
        cout << diameter << "\n";
    }
    return 0;
}

최종 코드

여기에서 확인하세요!

알고리즘 개선 방안

1번 방안

현재 구현한 것을 무방향 그래프로 바꾸고, 1번 방법으로 구현하는 것도 좋을 것 같습니다.

알고리즘, 종만북

알고리즘 종만북