순환선 지하철에서 두 역 사이의 최단 거리를 구하는 C++ 코드

문제 설명

두 개의 수 s와 t, 그리고 n개의 원소로 이루어진 배열 D가 있다고 가정해 보겠습니다. 드림랜드(Dreamland) 지하철의 순환선에는 n개의 서로 다른 역이 있으며, 인접한 역들 사이의 거리가 모두 주어져 있습니다. 즉, D[i]는 i번 역과 (i+1)번 역 사이의 거리를 나타내고, D[n-1]은 (n-1)번 역과 0번 역 사이의 거리를 의미합니다. 이때 s역에서 t역까지 이동할 때의 최단 거리를 구하는 것이 목표입니다.

예를 들어 입력이 s = 1, t = 3, D = [2, 3, 4, 9]라고 한다면, 출력 결과는 5가 됩니다.

접근 방법 및 알고리즘

순환선 위에서 두 역 사이를 이동하는 경로는 두 가지입니다. 어느 한 방향으로 진행하는 경우와 그 반대 방향으로 진행하는 경우입니다. 전체 둘레의 총 길이를 sum1이라 하고, 한쪽 방향의 거리 합을 sum2라고 하면 반대 방향의 거리는 (sum1 - sum2)가 됩니다. 따라서 두 값 중 더 작은 값이 바로 최단 거리입니다.

구체적인 풀이 절차는 다음과 같습니다.

n := 배열 D의 크기
크기가 (n + 1)인 배열 arr을 선언하고 모든 값을 0으로 초기화
i := 1부터 i <= n까지 i를 1씩 증가시키며 반복:
    arr[i] := D[i - 1]
    sum1 := sum1 + arr[i]
만약 s > t이면:
    s와 t의 값을 서로 교환(swap)
i := s부터 i < t까지 i를 1씩 증가시키며 반복:
    sum2 := sum2 + arr[i]
sum2와 (sum1 - sum2) 중 더 작은 값을 반환

C++ 구현 예제

아래 구현 예제를 통해 좀 더 쉽게 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(int s, int t, vector<int> D){
    int n = D.size(), sum1 = 0, sum2 = 0;
    vector<int> arr(n + 1, 0);
    for (int i = 1; i <= n; i++){
        arr[i] = D[i - 1];
        sum1 += arr[i];
    }
    if (s > t)
        swap(s, t);
    for (int i = s; i < t; i++)
        sum2 += arr[i];
    return min(sum2, sum1 - sum2);
}
int main(){
    int s = 1;
    int t = 3;
    vector<int> D = { 2, 3, 4, 9 };
    cout << solve(s, t, D) << endl;
}

입력

1, 3, { 2, 3, 4, 9 }

출력

5

결과 분석

s = 1이고 t = 3이므로, 1번 역에서 3번 역까지 한 방향으로 이동할 때의 거리는 D[0] + D[1] = 2 + 3 = 5입니다. 전체 둘레 길이는 2 + 3 + 4 + 9 = 18이므로 반대 방향으로 이동할 때의 거리는 18 - 5 = 13입니다. 두 값 중 더 작은 값인 5가 바로 최단 거리가 됩니다.