Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 주어진 경로에서 최소 정류장 수 구하기

문제 정의

2차원 평면상에 여러 개의 지점이 있으며, 이 지점들은 특정한 순서대로 방문해야 합니다. 한 지점에서 다른 지점으로 이동할 때는 항상 최단 경로를 선택하며, 경로의 각 구간은 격자선(grid line)에 평행하게 이루어집니다.

우리에게는 지점들을 방문하기 위해 선택된 경로가 문자열 형태로 주어집니다. 이때, 주어진 경로 전체를 생성하기 위해 반드시 필요한 최소 지점(정류장)의 개수를 구하는 것이 이 문제의 목표입니다.


알고리즘

  1. 지점을 방문할 때의 이동 패턴을 관찰하면 문제를 해결할 수 있습니다.
  2. 한 지점에서 다른 지점까지 최단 경로로 이동하려면, 이동 방향은 한 방향이거나 최대 두 방향만 사용해야 합니다. 예를 들어 'L'(왼쪽)과 'R'(오른쪽)을 동시에, 또는 'U'(위)와 'D'(아래)를 동시에 포함하는 구간은 더 이상 하나의 직선 구간으로 표현할 수 없으므로 새로운 정류장이 필요합니다.

구현 예제 (C++)

#include <bits/stdc++.h>
using namespace std;
int getMinStops(string path) {
    int n = path.length();
    map<char, int> directionMap;
    int stops = 1;
    for (int i = 0; i < n; ++i) {
        char direction = path[i];
        directionMap[direction] = 1;
        if ((directionMap['L'] && directionMap['R']) ||
        (directionMap['U'] && directionMap['D'])) {
            directionMap.clear();
            ++stops;
            directionMap[direction] = 1;
        }
    }
    return stops + 1;
}
int main() {
    string path = "LLUUULLDD";
    cout << "Minimum stops = " << getMinStops(path) << endl;
    return 0;
}

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.


출력 결과

Minimum stops = 3

동작 원리 설명

주어진 입력 경로는 LLUUULLDD입니다. 알고리즘은 경로를 한 글자씩 순회하면서 현재 구간에서 사용 중인 방향들을 directionMap에 기록합니다. 만약 서로 반대되는 방향('L'과 'R', 또는 'U'와 'D')이 동시에 나타나면, 해당 시점부터는 새로운 정류장에서 출발해야 하므로 정류장 수를 1 증가시키고 방향 기록을 초기화합니다.

마지막으로 시작 정류장 1개와 마지막 도착 지점 1개를 고려하여 총 정류장 수를 반환합니다. 위 예제에서는 총 3개의 정류장이 필요함을 확인할 수 있습니다.