[Pro] 긴 사다리 게임

문제

사다리 게임이다.

특정 가로줄을 추가 및 삭제할 수 있다. 특정 참가자가 총 몇 개의 가로줄을 지나는지, 사다리의 특정 좌표를 지나는 참가자가 누구인지 조회할 수 있어야 한다.

구현해야 하는 API는 다음과 같다.

void init();
void add(int mX, int mY);
void remove(int mX, int mY);
int numberOfCross(int mID);
int participant(int mX, int mY);

`init`

void init();

게임을 초기화한다.

세로줄은 1번부터 100번까지 존재한다.
참가자도 1번부터 100번까지 존재한다.
mID번 참가자는 mID번 세로줄의 맨 위에서 출발한다.
처음에는 가로줄이 하나도 없다.
이전 테스트에서 사용한 모든 정보를 초기화한다.

`add`

void add(int mX, int mY);

높이 mY에서 mX번 세로줄과 mX + 1번 세로줄을 연결하는 가로줄을 추가한다.

이후 해당 위치를 지나는 참가자는 가로줄을 따라 인접한 세로줄로 이동한다.

`remove`

void remove(int mX, int mY);

높이 mY에서 mX번 세로줄과 mX + 1번 세로줄을 연결하고 있는 가로줄을 삭제한다.

삭제된 가로줄은 이후 참가자의 이동에 영향을 주지 않는다.

`numberOfCross`

int numberOfCross(int mID);

mID번 참가자가 자신의 출발 위치에서 사다리의 맨 아래까지 이동하면서 지나가는 가로줄의 개수를 반환한다.

참가자가 최종적으로 어느 세로줄에 도착하는지가 아니라, 이동 과정에서 건넌 가로줄의 개수를 구한다.

`participant`

int participant(int mX, int mY);

현재 사다리에서 좌표 (mX, mY)를 지나는 참가자의 번호를 반환한다.

즉, 해당 위치를 지나가는 경로가 어느 참가자의 출발점에서 이어진 것인지 찾는다.

제약 사항은 다음과 같다.

세로줄과 참가자는 100개입니다.
사다리의 높이는 1,000,000,000입니다.
add()는 최대 200,000회 호출됩니다.
remove()는 최대 5,000회 호출됩니다.
numberOfCross()는 최대 500회 호출됩니다.
participant()는 최대 500회 호출됩니다.
어떤 참가자든 실제로 지나가는 가로줄의 개수는 최대 5,000개입니다.

설명

먼저 2차원 배열로 사다리를 관리해보자.

ladder[y][x] // 높이 y에서 x, x+1번 세로줄 사이 가로줄이 존재하는지

2차원 배열을 사용하면 사다리 추가 및 삭제는 단순하다. numberOfCross(), participant()는 높이를 실제로 거슬러 올라가며 구하면 된다.

단, 사다리 높이의 최댓값은 1,000,000,000인데, 세로줄 개수가 최대 100개이므로 그대로 2차원 배열에 저장하면 메모리 초과가 발생한다.

add()는 최대 200,000번 호출된다. 이는 곧 최대 가로줄의 개수를 의미한다. 높이는 10억이나 실제로 가로줄이 있는 높이는 많지 않다. 따라서 좌표를 저장하는 것이 아니라, 각 세로줄에서 존재하는 가로줄의 y좌표를 저장한다.

set<int> line[101]; // line[x]: x번 세로줄과 연결된 가로줄의 높이들

가로줄을 추가하거나 삭제하면 단순히 x, x+1번 세로줄에서 가로줄이 위치한 높이를 추가 또는 삭제하면 된다. 이는 $O(logN)$ 에 처리 가능하다.

특정 참가자가 높이 y에 있다고 할 때, y보다 아래에 있는 가장 가까운 가로줄은 upper_bound를 사용하면 쉽게 구할 수 있다. numberOfCross()는 그렇게 구현하면 된다. participant() 역시 비슷한 방식으로 구현하면 된다.

이렇게만 구현해도 통과하나, 매번 다음 가로줄을 $O(logN)$ 으로 찾는 것이 병목이 될 수 있다. 어차피 가로줄에 도착하면 다음에 이동할 가로줄은 이미 정해져 있으므로, 가로줄을 이중 연결 리스트로 연결하면 $O(1)$ 에 처리할 수 있다.

다만 가로줄을 추가할 때, 추가할 위치 위에 있는 가로줄의 y좌표를 알아야 한다. 가로줄 노드끼리 연결해야 하기 때문이다. 연결 리스트만 사용한다면 직접 탐색해야 하므로 느리다. 따라서 특정 세로줄에 존재하는 가로줄과의 교점을 저장하기 위해 map을 사용한다. 노드 간 연결을 위해 근처 노드를 찾는 데 $O(logN)$ 이면 찾을 수 있다. 가로줄 삭제 역시 마찬가지이다.

map<int, list<int>::iterator> nodeMap[101]; // nodeMap[x][y]: x번 세로줄의 높이 y에 있는 교점이 실제 list의 어느 원소인지

코드

#include <map>

using namespace std;

#define MAX_LINE 100
#define MAX_NODE 400210
#define MAX_Y 1000000000

map<int, int> nodeMap[MAX_LINE + 1];

int prevNode[MAX_NODE];
int nextNode[MAX_NODE];

int nodeCnt;

void link(int front, int back)
{
    nextNode[front] = back;
    prevNode[back] = front;
}

void init()
{
    for (int i = 1; i <= MAX_LINE; i++)
    {
        nodeMap[i].clear();

        int start = i;
        int end = MAX_LINE + i;

        nodeMap[i][0] = start;
        nodeMap[i][MAX_Y] = end;

        link(start, end);
    }

    nodeCnt = MAX_LINE * 2 + 1;
}

void add(int mX, int mY)
{
    int nowLeft = nodeCnt++;
    int nowRight = nodeCnt++;

    auto leftIt = nodeMap[mX].upper_bound(mY);
    auto rightIt = nodeMap[mX + 1].upper_bound(mY);

    --leftIt;
    --rightIt;

    int prevLeft = leftIt->second;
    int prevRight = rightIt->second;

    int nextLeft = nextNode[prevLeft];
    int nextRight = nextNode[prevRight];

    link(prevLeft, nowRight);
    link(nowRight, nextRight);

    link(prevRight, nowLeft);
    link(nowLeft, nextLeft);

    nodeMap[mX][mY] = nowLeft;
    nodeMap[mX + 1][mY] = nowRight;
}

void remove(int mX, int mY)
{
    int nowLeft = nodeMap[mX][mY];
    int nowRight = nodeMap[mX + 1][mY];

    int prevLeft = prevNode[nowRight];
    int prevRight = prevNode[nowLeft];

    int nextLeft = nextNode[nowLeft];
    int nextRight = nextNode[nowRight];

    link(prevLeft, nextLeft);
    link(prevRight, nextRight);

    nodeMap[mX].erase(mY);
    nodeMap[mX + 1].erase(mY);
}

int numberOfCross(int mID)
{
    int now = mID;
    int ret = -1;

    while (now <= MAX_LINE || now > MAX_LINE * 2)
    {
        ret++;
        now = nextNode[now];
    }

    return ret;
}

int participant(int mX, int mY)
{
    auto it = nodeMap[mX].upper_bound(mY);
    --it;

    int now = it->second;

    while (now > MAX_LINE)
        now = prevNode[now];

    return now;
}

시간복잡도

add()의 호출 횟수를 A, 존재하는 가로줄의 수를 H, 실제로 지나가는 가로줄의 수를 K라고 하자.

init()은 map에 저장하는 모든 원소를 제거하므로 $O(H)$ 이다.

add()는 map에 가로줄을 삽입하는데 $O(logH)$ , 두 노드를 연결하는데 $O(1)$ 이다. remove()도 마찬가지이다.

numberOfCross()는 가로줄을 K개 지나고, 노드 간 이동은 $O(1)$ 이므로 총 $O(K)$ 이다.

participant()는 바로 위 교점을 찾는데 $O(logH)$ , 노드를 따라 거슬러 올라가는데 $O(K)$ 이다.

공간복잡도

$H <= A$ 이므로 $O(A)$ 이다.