C++ 그리디 알고리즘으로 정차 가능한 최대 열차 수 구하기

문제 설명

이 문제에서는 한 역이 보유한 승강장 수를 나타내는 값 N이 주어지며, 각 승강장에는 두 개의 선로가 있습니다. 또한 T개의 열차가 해당 역을 지나가며, 각 열차의 도착 시간과 출발 시간이 함께 주어집니다. 모든 열차는 특정 승강장에 정차하도록 지정되어 있습니다. 우리의 목표는 C++로 정차를 제공할 수 있는 최대 열차 수를 구하는 프로그램을 작성하는 것입니다.

예시를 통해 문제를 살펴보겠습니다.

입력

N = 3, T = 5
Trains = {{0915, 0930, 2}, {0930, 0945, 3}, {0930, 1200, 1}, {0910, 0925, 3}, {0940, 1015, 1}}

출력

설명

열차 운행 일정은 다음과 같습니다.
열차 1 : 2번 승강장 정차 — 09:15 ~ 09:30
열차 2 : 3번 승강장 정차 — 09:30 ~ 09:45
열차 3 : 정차하지 않음
열차 4 : 3번 승강장 정차 — 09:10 ~ 09:25
열차 5 : 1번 승강장 정차 — 09:40 ~ 10:15

위 예시에서는 시간대가 서로 겹치지 않도록 배정할 수 있는 열차가 총 4개이므로 정답은 4가 됩니다.

해결 접근 방법

이 문제는 역에 정차할 수 있는 최대한 많은 열차를 찾아야 하므로 탐욕(Greedy) 알고리즘을 적용하는 것이 가장 효과적입니다.

널리 알려진 활동 선택(Activity Selection) 문제와 동일한 원리로 최적해를 구할 수 있습니다. 각 승강장마다 열차 정보를 저장할 벡터를 생성한 뒤, 출발 시간을 기준으로 정렬하고 시간대가 겹치지 않는 열차를 순서대로 선택하면 됩니다. 전체 알고리즘은 다음과 같습니다.

각 열차의 (출발 시간, 도착 시간) 정보를 배정된 승강장 번호의 벡터에 저장합니다.
모든 승강장의 열차 목록을 출발 시간 기준으로 오름차순 정렬합니다.
각 승강장에서 첫 번째 열차를 선택한 뒤, 다음 열차의 도착 시간이 직전에 선택한 열차의 출발 시간보다 늦거나 같으면 해당 열차를 추가로 선택합니다.
모든 승강장에서 선택된 열차 수를 합산하면 그것이 곧 정답이 됩니다.

이 방법의 시간 복잡도는 정렬 단계가 지배적이므로 O(T log T)입니다.

구현 예제

다음은 위 접근 방법을 그대로 구현한 C++ 프로그램입니다.

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

int maxStop(int trains[][3], int N, int T) {
    vector<pair<int, int> > tStopping[N + 1];
    int trainsStopped = 0;

    // 각 열차를 배정된 승강장 벡터에 (출발 시간, 도착 시간) 형태로 저장
    for (int i = 0; i < T; i++)
        tStopping[trains[i][2]].push_back(make_pair(trains[i][1], trains[i][0]));

    // 승강장별 열차 목록을 출발 시간 기준으로 정렬
    for (int i = 0; i <= N; i++)
        sort(tStopping[i].begin(), tStopping[i].end());

    // 각 승강장에서 시간대가 겹치지 않게 최대한 많은 열차 선택
    for (int i = 0; i <= N; i++) {
        if (tStopping[i].size() == 0)
            continue;
        int a = 0;
        trainsStopped++;
        for (int j = 1; j < tStopping[i].size(); j++) {
            if (tStopping[i][j].second >= tStopping[i][a].first) {
                a = j;
                trainsStopped++;
            }
        }
    }
    return trainsStopped;
}

int main() {
    int N = 3;
    int T = 5;
    int trains[T][3] = {{915, 930, 2}, {930, 945, 3}, {930, 1200, 1}, {910, 925, 3}, {940, 1015, 1}};
    cout << "The Maximum No. of Trains Stopped at the station is " << maxStop(trains, N, T);
    return 0;
}

출력 결과

The Maximum No. of Trains Stopped at the station is 4

실행 결과, 시간대가 겹치지 않도록 배정할 수 있는 최대 열차 수인 4가 정상적으로 출력되는 것을 확인할 수 있습니다.