[BOJ] 백준 2983 개구리 공주

출처: https://www.acmicpc.net/problem/2983

 Input 

7 5

ACDBB

5 6

8 9

4 13

1 10

7 4

10 9

3 7

 

 Output 

7 4

식물들의 위치는 아래와 같습니다.

[Jungol] 1889 N Queen 문제에서도 이용했지만

[Jungol] 정올 1889 N Queen

2차원 평면에서 같은 선상의 대각선상에 위치한 것은 아래와 같이 알 수 있습니다.

 

▶ (x, y) 일 때 x + y 결과가 동일

    ex) (7, 6) ↔ (8, 5) ↔ (6, 7) ▷ x + y = 13

▶ (x, y) 일 때 x - y 결과가 동일

    ex) (7, 6) ↔ (8, 7) ↔ (6, 5) ▷ x - y = 1

    ex) (3, 4) ↔ (2, 3) ↔ (4, 5) ▷ x - y = -1

 

개구리의 점프방향을 대각선 방향으로 한 지점당 4개의 연결리스트로 식물들을 연결합니다.

식물의 최대 개수 = 100,000 → 위치(x, y)와 4개의 포인터를 가지는 구조체

 

Q) 식물들의 위치(x, y)가 주어졌을 때, 어떻게 같은 대각선상의 오름차순으로 맞출 수 있을까?

    주어진 식물의 위치를 x-y, x+y 기준으로 정렬합니다. (같은 값인 경우 x좌표 기준으로 정렬)

ex) (5, 6) (8, 9) (4, 13) (1, 10) (7, 4) (10, 9) (3, 7)

[x-y기준] A, D 방향 연결

: (1, 10) ↔ (4, 13)   (3, 7)   (5, 6) ↔ (8, 9)  (10, 9)   (7, 4)

[x-y기준] A, D 방향 연결

: (3, 7)  (1, 10) ↔ (5, 6) ↔ (7, 4)  (4, 13) ↔ (8, 9)   (10, 9)

 

식물간의 연결이 구현되었다면, 첫번째 식물을 출발점으로 해서

점프하고자 하는 방향에 식물이 있으면 점프 후 식물 제거(연결 처리)하며 주어진 명령만큼 점프합니다.

주의) 개구리가 동작을 멈추는 순간은 점프 방향에 식물이 없거나 모든 점프가 종료되었을 경우입니다.

        점프 방향에 식물이 없는 경우는 제자리에 위치하는 것이므로 

        점프 횟수가 남아 있다면 다른 방향으로 점프를 시도할 수 있습니다.

 

---

#include <stdio.h>
 
const int MAX_N = 1e5;
int N, K;
char cmd[MAX_N + 10]; // 선택한 방향(명령)
int idx[MAX_N + 10], tmp[MAX_N + 10];
struct NODE {
    int x, y; // 식물 좌표
    NODE *A, *B, *C, *D;
}leaf[MAX_N + 10];
NODE* frog;
 
int compDiff(int a, int b) {
    int diff_A = leaf[a].x - leaf[a].y;
    int diff_B = leaf[b].x - leaf[b].y;
    if (diff_A == diff_B) return leaf[a].x < leaf[b].x;
    return diff_A < diff_B;
}
 
int compSum(int a, int b) {
    int sum_A = leaf[a].x + leaf[a].y;
    int sum_B = leaf[b].x + leaf[b].y;
    if (sum_A == sum_B) return leaf[a].x < leaf[b].x;
    return sum_A < sum_B;
}
 
void mergesort(int start, int end, int (*comp)(int, int)) {
    if (start >= end)
        return;
    int i = start, k = start, mid = (start + end) / 2, j = mid + 1;
    mergesort(start, mid, comp);
    mergesort(mid + 1, end, comp);
    while ((i <= mid) && (j <= end)) {
        if (comp(idx[i], idx[j])) tmp[k++] = idx[i++];
        else tmp[k++] = idx[j++];
    }
    while (i <= mid) tmp[k++] = idx[i++];
    while (j <= end) tmp[k++] = idx[j++];
    for (i = start; i <= end; i++)
        idx[i] = tmp[i];
}
 
void input() {
    scanf("%d %d", &N, &K);
    scanf("%s", cmd);
    for (int i = 1; i <= N; i++) {
        scanf("%d %d", &leaf[i].x, &leaf[i].y);
        leaf[i].A = leaf[i].B = leaf[i].C = leaf[i].D = NULL;
    }
}
 
void connectLeaf() {
    // 인덱스만 정렬
    for (int i = 1; i <= N; i++) {
        idx[i] = i;
    }
 
    // A, D 연결
    mergesort(1, N, compDiff);
    for (int i = 1; i < N; i++) {
        NODE* cur = &leaf[idx[i]];
        NODE* next = &leaf[idx[i + 1]];
        // 같은 대각선상인 경우
        if ((cur->x - cur->y) == (next->x - next->y)) {
            cur->A = next;
            next->D = cur;
        }
    }
 
    // B, C 연결
    mergesort(1, N, compSum);
    for (int i = 1; i < N; i++) {
        NODE* cur = &leaf[idx[i]];
        NODE* next = &leaf[idx[i + 1]];
        // 같은 대각선상인 경우
        if ((cur->x + cur->y) == (next->x + next->y)) {
            cur->B = next;
            next->C = cur;
        }
    }
}
 
void delNodeLink(NODE* p) {
    // 실제 leaf[]를 free하지 않고 연결만 조정
    if (p->A) p->A->D = p->D;
    if (p->D) p->D->A = p->A;
    if (p->B) p->B->C = p->C;
    if (p->C) p->C->B = p->B;
}
 
void jumpFrog() {
    frog = &leaf[1];
 
    for (int i = 0; i < K; i++) {
        if (cmd[i] == 'A') {
            if (frog->A) {
                delNodeLink(frog);
                frog = frog->A;
            }
        }
        else if (cmd[i] == 'B') {
            if (frog->B) {
                delNodeLink(frog);
                frog = frog->B;
            }
        }
        else if (cmd[i] == 'C') {
            if (frog->C) {
                delNodeLink(frog);
                frog = frog->C;
            }
        }
        else if (cmd[i] == 'D') {
            if (frog->D) {
                delNodeLink(frog);
                frog = frog->D;
            }
        }
    }
    printf("%d %d\n", frog->x, frog->y);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    connectLeaf();
    jumpFrog();
}