[Baekjoon] 2568 – 전깃줄 2

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

전깃줄이 서로 엉켜있는 모습을 상상해보세요. 두 전봇대 사이에 여러 개의 전깃줄이 연결되어 있는데, 일부는 서로 교차하여 합선의 위험을 만들고 있습니다. 이 문제는 교차하는 전깃줄들 중 최소한의 개수만 제거하여 나머지 전깃줄들이 모두 평행하게 만드는 것이 목표입니다.

문제를 좀 더 구체적으로 살펴보면, 각 전깃줄은 A 전봇대의 특정 위치와 B 전봇대의 특정 위치를 연결합니다. 예를 들어 A의 1번과 B의 8번이 연결되고, A의 3번과 B의 2번이 연결된다면, 이 두 전깃줄은 교차하게 됩니다. 왜냐하면 A에서는 1번이 3번보다 위에 있지만, B에서는 8번이 2번보다 아래에 있기 때문입니다.

핵심은 전깃줄이 교차하지 않으려면, A 전봇대에서의 순서와 B 전봇대에서의 순서가 일치해야 한다는 점입니다. 즉, A에서 위에 있는 전깃줄이 B에서도 위에 있어야 합니다.

🧠 직관적 접근법과 그 한계

가장 먼저 떠오르는 방법은 모든 전깃줄 쌍을 확인하여 교차하는 경우를 찾고, 이들 중에서 최소한의 전깃줄만 제거하는 조합을 찾는 것입니다. 이는 각 전깃줄에 대해 “제거할 것인가, 남길 것인가”를 결정하는 2<sup>N</sup> 가지 경우를 모두 탐색하는 방식으로 이어집니다.

하지만 전깃줄의 개수가 최대 100,000개까지 주어질 수 있다는 제약을 고려하면, 이런 완전탐색 방식은 현실적으로 불가능합니다. 2<sup>100000</sup>은 상상할 수 없을 정도로 큰 수이며, 현존하는 어떤 컴퓨터로도 합리적인 시간 내에 계산할 수 없습니다. 심지어 N = 30만 되어도 10억 번 이상의 연산이 필요하여 시간 초과가 발생할 것입니다.

🤔 문제의 본질을 찾아가는 사고 과정

여기서 중요한 관찰이 시작됩니다. 교차하지 않는 전깃줄들의 집합이 어떤 특성을 가지는지 더 자세히 분석해보겠습니다.

두 전깃줄이 교차하지 않는다는 것은 무엇을 의미할까요? 전깃줄 (a1, b1)과 (a2, b2)를 생각해봅시다. 만약 a1 < a2라면 (즉, 첫 번째 전깃줄이 A 전봇대에서 더 위에 있다면), 교차하지 않기 위해서는 반드시 b1 < b2여야 합니다 (B 전봇대에서도 더 위에 있어야 함). 마찬가지로 a1 > a2라면 b1 > b2여야 합니다.

이를 일반화하면, 교차하지 않는 전깃줄들의 집합에서는 A 전봇대에서의 순서와 B 전봇대에서의 순서가 정확히 일치해야 합니다. 다시 말해, A 전봇대 기준으로 전깃줄들을 정렬했을 때, 해당하는 B 전봇대의 위치들도 오름차순으로 정렬되어 있어야 한다는 뜻입니다.

🔍 핵심 통찰: 순서의 일치성

여기서 결정적인 깨달음이 옵니다. 문제를 다음과 같이 재구성할 수 있습니다:

  1. 1단계: 모든 전깃줄을 A 전봇대 위치를 기준으로 오름차순 정렬합니다.
  2. 2단계: 정렬된 순서대로 B 전봇대 위치들을 나열하면 하나의 수열이 됩니다.
  3. 3단계: 이 수열에서 가장 긴 증가하는 부분 수열을 찾으면, 그것이 바로 교차하지 않으면서 최대한 많이 남길 수 있는 전깃줄들에 해당합니다!

왜 그럴까요? A 전봇대 기준으로 이미 정렬되어 있는 상황에서, B 전봇대 위치들이 증가하는 순서를 유지한다면, 이는 곧 A와 B 모두에서 순서가 일치한다는 의미이기 때문입니다. 그리고 이러한 부분 수열이 가장 길수록, 교차하지 않으면서 남길 수 있는 전깃줄의 개수가 최대가 됩니다.

구체적인 예시로 이해해보겠습니다. 전깃줄들이 다음과 같다고 가정해봅시다:

  • (1, 8), (2, 2), (3, 9), (4, 1), (5, 4), (6, 6), (7, 7), (8, 3)

A 전봇대 기준으로 정렬하면 이미 정렬된 상태입니다. 이제 B 전봇대 위치들을 순서대로 나열하면: [8, 2, 9, 1, 4, 6, 7, 3]

이 수열에서 가장 긴 증가 부분 수열을 찾아야 합니다. 예를 들어 [1, 4, 6, 7] 또는 [2, 4, 6, 7] 등이 가능한 LIS입니다. 길이가 4이므로, 최대 4개의 전깃줄을 교차 없이 남길 수 있고, 따라서 8 – 4 = 4개의 전깃줄을 제거해야 합니다.

🌟 기하학에서 수열론으로의 변환

이 과정에서 우리는 본질적으로 기하학적 교차 문제를 수열의 순서 문제로 변환했습니다. 이는 문제 해결에서 매우 중요한 기법 중 하나입니다. 복잡해 보이는 기하학적 조건을 수학적으로 더 다루기 쉬운 형태로 바꾸어 놓은 것입니다.

원래 문제에서는 “두 선분이 교차하는가?”라는 기하학적 질문을 다뤘지만, 변환 후에는 “두 수가 순서를 유지하는가?”라는 훨씬 단순한 비교 연산으로 바뀌었습니다. 이러한 변환은 알고리즘의 복잡성을 크게 줄여줍니다.

📘 최장 증가 부분 수열(LIS)에 대하여
최장 증가 부분 수열은 주어진 수열에서 원소들의 순서를 유지하면서 선택할 수 있는 가장 긴 증가하는 부분 수열을 의미합니다. 전통적인 동적 계획법으로는 O(N²) 시간이 걸리지만, 이진 탐색을 활용하면 O(N log N)으로 최적화할 수 있습니다. 핵심 아이디어는 각 길이별로 가능한 가장 작은 마지막 원소를 유지하는 것입니다.

🔍 상세한 알고리즘 동작 과정

구체적인 예시로 알고리즘의 동작을 살펴보겠습니다. 다음과 같은 전깃줄들이 있다고 가정해보겠습니다.

  • (1, 8), (2, 2), (3, 9), (4, 1), (5, 4), (6, 6), (7, 7), (8, 3)

먼저 A 전봇대 기준으로 정렬하면 이미 정렬된 상태입니다. 이제 B 전봇대의 연결점들을 순서대로 나열하면 [8, 2, 9, 1, 4, 6, 7, 3]이 됩니다. 이 수열에서 최장 증가 부분 수열을 찾아야 합니다.

LIS 알고리즘을 단계별로 적용해보겠습니다:

  1. 8 처리: dp = [8]
  2. 2 처리: 2 < 8이므로 dp[0] = 2로 교체, dp = [2]
  3. 9 처리: 9 > 2이므로 추가, dp = [2, 9]
  4. 1 처리: 1 < 2이므로 dp[0] = 1로 교체, dp = [1, 9]
  5. 4 처리: 1 < 4 < 9이므로 dp[1] = 4로 교체, dp = [1, 4]
  6. 6 처리: 6 > 4이므로 추가, dp = [1, 4, 6]
  7. 7 처리: 7 > 6이므로 추가, dp = [1, 4, 6, 7]
  8. 3 처리: 1 < 3 < 4이므로 dp[1] = 3으로 교체, dp = [1, 3, 6, 7]

최종적으로 LIS의 길이는 4이므로, 교차하지 않게 남겨둘 수 있는 전깃줄의 최대 개수는 4개입니다. 전체 8개에서 4개를 빼면 제거해야 할 전깃줄은 4개입니다.

실제 LIS를 복원하기 위해서는 역추적 정보도 저장해야 합니다. 각 원소에 대해 그 이전 원소가 무엇인지 기록해두면, 나중에 거꾸로 따라가며 실제 수열을 재구성할 수 있습니다.

💻 완전한 구현 코드

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    <em>// 전깃줄 정보를 저장: (A전봇대 위치, B전봇대 위치)</em>
    vector<pair<int,int>> A(N);
    <em>// B전봇대 위치를 키로 하여 A전봇대 위치를 저장하는 맵</em>
    unordered_map<int,int> mp;
    
    for (int i = 0; i < N; ++i) {
        cin >> A[i].first >> A[i].second;
        <em>// B전봇대 위치 → A전봇대 위치 매핑 저장 (나중에 역추적에 사용)</em>
        mp[A[i].second] = A[i].first;
    }
    
    <em>// A전봇대 위치를 기준으로 전깃줄들을 오름차순 정렬</em>
    sort(A.begin(), A.end());
    
    <em>// LIS를 구하기 위한 dp 배열: 각 길이별 가능한 최소 끝값 저장</em>
    vector<int> dp;
    <em>// 역추적을 위한 parent 배열: p[x] = x의 이전 원소</em>
    vector<int> p(500001, -1);
    <em>// LIS의 마지막 원소를 추적하기 위한 변수</em>
    int last = -1;
    
    for (int i = 0; i < N; ++i) {
        int curr = A[i].second; <em>// 현재 전깃줄의 B전봇대 연결 위치</em>
        
        <em>// dp 배열에서 curr보다 크거나 같은 첫 번째 원소의 위치를 찾음</em>
        int idx = lower_bound(dp.begin(), dp.end(), curr) - dp.begin();
        
        if (idx == (int)dp.size()) {
            <em>// curr가 dp의 모든 원소보다 크므로 새로운 길이 추가</em>
            dp.push_back(curr);
            last = curr; <em>// 가장 긴 LIS의 마지막 원소 갱신</em>
        } else if (curr < dp[idx]) {
            <em>// 같은 길이에서 더 작은 끝값으로 갱신</em>
            dp[idx] = curr;
        }
        
        <em>// 역추적을 위한 parent 관계 설정</em>
        if (idx > 0) {
            p[curr] = dp[idx-1]; <em>// curr의 바로 이전 원소는 dp[idx-1]</em>
        }
    }
    
    <em>// 실제 LIS에 포함된 B전봇대 위치들을 역추적으로 찾기</em>
    unordered_set<int> v; <em>// LIS에 포함된 A전봇대 위치들을 저장</em>
    
    while(last != -1) {
        <em>// B전봇대 위치를 A전봇대 위치로 변환하여 저장</em>
        v.insert(mp[last]);
        <em>// 이전 원소로 이동</em>
        last = p[last];
    }
    
    <em>// 제거해야 할 전깃줄의 개수 = 전체 개수 - LIS 길이</em>
    cout << N - v.size() << "\n";
    
    <em>// LIS에 포함되지 않은 전깃줄들의 A전봇대 위치를 출력</em>
    for (int i = 0; i < N; ++i) {
        if (v.find(A[i].first) == v.end()) {
            cout << A[i].first << "\n";
        }
    }
    
    return 0;
}

🔁 대안적 접근법

이 문제는 다른 방식으로도 해석할 수 있습니다. 좌표압축을 통해 B전봇대의 위치들을 1부터 N까지의 연속된 정수로 매핑한 후, A전봇대 순서로 정렬된 상태에서 각 위치에 해당하는 압축된 B값들의 LIS를 구하는 방법도 있습니다. 이 접근법은 메모리 사용량을 줄일 수 있다는 장점이 있지만, 본질적으로는 동일한 알고리즘입니다.

또한 세그먼트 트리나 펜윅 트리를 활용한 O(N log N) 해법도 존재합니다. 이는 좌표압축 후 각 위치에서 가능한 최대 LIS 길이를 트리 구조를 통해 효율적으로 관리하는 방식입니다. 다만 구현이 더 복잡하고 이 문제에서는 이진 탐색 기반 LIS가 더 직관적이고 효율적입니다.

📌 핵심 아이디어와 배운점

이 문제의 핵심은 겉보기에는 기하학적 교차 문제처럼 보이지만, 실제로는 순서 관계를 다루는 조합론적 문제라는 점입니다. A전봇대를 기준으로 정렬한 후 B전봇대 순서에서 최장 증가 부분 수열을 찾는다는 변환이 이 문제를 해결하는 열쇠였습니다.

또한 이진 탐색을 활용한 LIS 알고리즘의 강력함을 다시 한번 확인할 수 있었습니다. O(N²) 동적 계획법을 O(N log N)으로 최적화할 수 있는 이 기법은 많은 실전 문제에서 시간 복잡도 병목을 해결하는 중요한 도구입니다. 역추적을 통해 실제 수열을 복원하는 기법도 함께 익혀두면 다양한 응용 문제에서 유용하게 활용할 수 있을 것입니다.

Similar Posts