[ABC273 D] LRUD Instructions

난이도: 1119

 

태그

• Implementation (구현 난이도 조금 있는 편)
• Coordinate Compression
• Binary Search

 

풀이

1. 1차원 버전의 문제를 풀어보자.

\( 1 \)부터 \( X \)까지의 칸이 있고, 여기에는 \( N \)개의 장애물이 있다고 해봅시다.

\( i \)번째 장애물은 \( P_{i} \)에 위치해있으며, 우리가 처리해야 하는 쿼리는

\( dir \) \( x \) \( l \): \( x \)에서 출발해서 \( dir \) 방향으로 \( l \)칸 이동 후 도착하는 위치 출력

입니다.

 

모든 쿼리에 대해, 이동 결과는 아래 셋 중 하나로 나오게 됩니다.

• \( l \)칸을 이동하는 동안 장애물을 만나지 않음
• 장애물을 만나서 도중에 멈춤
• 마지막 칸에 다다라서 멈춤

 

잠시 \( dir \)이 R로 고정되었다고 해봅시다.

그럼, 각각의 경우에 대한 최종 위치는 아래와 같이 표현할 수 있습니다.

• \( l \)칸을 이동하는 동안 장애물을 만나지 않음: \( x+l \)
• 장애물을 만나서 도중에 멈춤: \( \min\limits_{x<P_{i}} P_{i} - 1 \)
• 마지막 칸에 다다라서 멈춤: \( X \)

 

최종적으로 멈추게 되는 위치는 위 셋 중 최솟값의 위치가 됩니다.

 

\( dir \)이 L인 경우는 R인 경우와 비슷하니, 비슷하게 처리해주면 됩니다.

 

2. 2차원으로 확장시켜봅시다.

문제에서 주는 상황은 2차원이기 때문에, 좀 더 생각이 필요할 거 같습니다.

 

그런데, 가능한 이동 방향은 항상 \( y \)축 또는 \( x \)축에 평행합니다.

이게 중요한 이유는, \( x \)축에 평행한 이동은 \( y \)좌표가 시작할 때의 \( y \)와 동일한 장애물만 남긴 뒤 1차원의 이동을 적용시키면 됩니다.

\( y \)축의 이동도 비슷하게 처리해주면 되겠죠.

 

3. 구현 디테일

위를 처리하는 가장 간단한 방법은 \( Y_{x} \) = 고정된 \( x \)에 대해 \( (y, x) \)가 장애물인 모든 \( y \)의 위치 를 저장하고, (\( X_y \)도 비슷한 방식으로 저장)

\( y \) 방향으로 이동할 때는 [1]에서 고려한 3가지를 계산해주는 것입니다.

 

이 때 2번째 경우 (장애물을 만나서 멈추는 경우)는 효율적으로 구현하기 위해서는 \( Y \) 배열에서 이진 탐색을 진행해줘야겠죠.

 

하지만 좌표의 범위가 \( 10^9 \)까지 갈 수 있으니, 뭔가가 더 필요해 보입니다.

 

생각해보면, 좌표의 범위가 \( 10^9 \)까지 가더라도, 장애물의 개수는 최대한 \( 200\,000 \)개이기 때문에

대부분의 좌표에 대해서는 "장애물 없음", 즉 \( Y \) 배열을 고려할 필요 없음 이 됩니다.

 

그러니, 실제로 장애물이 있는 \( y, x \)좌표들에 대해 좌표 압축을 해주고, 이 값을 \( Y \)의 인덱스로 넣어주면 됩니다.

만약 인덱스에 없는 값이 나왔다면, 장애물이 없는 것이니 패스해주면 되죠.

 

4. 구현

map<int, int> cvty, cvtx; set<int> sy, sx;
vector<int> vy[200020], vx[200020];
 
pi2 arr[200020];
 
void Main(){
    int h, w, y, x; cin >> h >> w >> y >> x;
    int n; cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> arr[i].fr >> arr[i].sc;
        sy.insert(arr[i].fr); sx.insert(arr[i].sc);
    }
    int cy = 0; for (int a : sy){ cvty[a] = ++cy; }
    int cx = 0; for (int a : sx){ cvtx[a] = ++cx; }
    for (int i = 1; i <= n; i++){
        vy[ cvtx[arr[i].sc] ].push_back(arr[i].fr);
        vx[ cvty[arr[i].fr] ].push_back(arr[i].sc);
    }
    for (int i = 1; i <= cy; i++){ sort(all(vx[i])); }
    for (int i = 1; i <= cx; i++){ sort(all(vy[i])); }
    int q; cin >> q; while (q--){
        char dir; int dst; cin >> dir >> dst;
        if (dir == 'U'){
            if (cvtx.count(x) == 0){ y = max(y-dst, 1); }
            else{
                int px = cvtx[x];
                auto idx = lower_bound(all(vy[px]), y) - vy[px].begin();
                y = max(y-dst, (idx==0 ? 1 : vy[px][idx-1]+1));
            }
        }
        if (dir == 'D'){
            if (cvtx.count(x) == 0){ y = min(y+dst, h); }
            else{
                int px = cvtx[x];
                auto idx = lower_bound(all(vy[px]), y) - vy[px].begin();
                y = min(y+dst, (idx==vy[px].size() ? h : vy[px][idx]-1));
            }
        }
        if (dir == 'L'){
            if (cvty.count(y) == 0){ x = max(x-dst, 1); }
            else{
                int py = cvty[y];
                auto idx = lower_bound(all(vx[py]), x) - vx[py].begin();
                x = max(x-dst, (idx==0 ? 1 : vx[py][idx-1]+1));
            }
        }
        if (dir == 'R'){
            if (cvty.count(y) == 0){ x = min(x+dst, w); }
            else{
                int py = cvty[y];
                auto idx = lower_bound(all(vx[py]), x) - vx[py].begin();
                x = min(x+dst, (idx==vx[py].size() ? w : vx[py][idx]-1));
            }
        }
        cout << y << ' ' << x << endl;
    }
}