C++에서 주어진 이동 구간을 통해 끝점에 도달할 수 있는지 확인하는 방법

문제 개요

x축 위에 n개의 점이 있고, 점들 사이에서 허용된 이동(transactions) 목록이 주어진다고 가정해 봅시다. 이때 허용된 이동만을 사용하여 시작 지점에서 끝 지점까지 도달할 수 있는지 판별하는 것이 문제입니다.

두 점 x1과 x2 사이의 이동이 허용되어 있다면, 현재 위치한 점 x에서 x1과 x2 사이의 임의의 중간 지점으로 이동할 수도 있고, x2로 곧바로 이동할 수도 있습니다.

예를 들어 n = 5이고, 허용된 이동 구간이 0→2, 2→4, 3→5라고 해 보겠습니다. 이 경우 출력은 YES입니다. 0→2→3→5로 이어지는 경로가 존재하기 때문입니다.

접근 방법

이 문제는 정렬과 그리디(greedy) 기법을 활용해 효율적으로 해결할 수 있습니다.

1. 먼저 각 쌍(pair)의 첫 번째 요소를 기준으로 목록을 오름차순으로 정렬합니다.
2. 목록의 두 번째 쌍부터 순회하면서, 현재 쌍의 첫 번째 요소가 이전 쌍의 두 번째 요소보다 작거나 같은지, 즉 구간이 서로 겹치거나 이어지는지 확인합니다.
3. 구간이 이어진다면 도달 가능 범위의 끝(end_point)을 현재 쌍의 두 번째 요소와 비교하여 더 큰 값으로 갱신함으로써 도달 범위를 확장합니다.
4. 순회가 끝난 후, 도달한 지점이 목적지(n) 이상인지와 시작점이 0인지를 함께 확인합니다. 두 조건을 모두 만족하면 YES를, 그렇지 않으면 NO를 출력합니다.

정렬에 O(n log n)의 시간이 소요되고 이후 순회는 O(n)이므로, 전체 시간 복잡도는 O(n log n)입니다.

예제 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 시작점에서 끝점까지 도달 가능한지 확인하는 함수
bool isPathPairFound(int n, vector<pair<int, int>> arr) {
    sort(arr.begin(), arr.end()); // 첫 번째 요소 기준으로 정렬
    int start_point = arr[0].first;
    int end_point = arr[0].second;
    for (int i = 1; i < (int)arr.size(); i++) {
        if (arr[i].first > end_point) // 구간이 끊기면 탐색 종료
            break;
        end_point = max(end_point, arr[i].second); // 도달 범위 확장
    }
    // 끝점까지 도달했는지, 시작점이 0인지 확인
    return (n <= end_point && start_point == 0);
}

int main() {
    vector<pair<int, int>> arr;
    arr.push_back(make_pair(0, 2));
    arr.push_back(make_pair(2, 4));
    arr.push_back(make_pair(3, 5));
    if (isPathPairFound(5, arr))
        cout << "Path has found";
    else
        cout << "NO Path has found";
    return 0;
}

실행 결과

Path has found

프로그램은 시작점(0)에서 목적지(5)까지 이어지는 경로를 성공적으로 찾아냈습니다. 구간들이 끊김 없이 연결되어 있으므로 중간 어느 지점으로든 자유롭게 이동할 수 있다는 점이 핵심입니다.