트리 탐색기 (백준 31406)

안녕하세요. 오늘은 파일을 열어볼 거예요.

문제

https://www.acmicpc.net/problem/31406

아이디어

sum[i]를 i번째 폴더를 포함해서 그 폴더가 가지고 있는 총 폴더의 개수라고 합시다. 당연하지만 닫혀있으면 sum[i]=1이고 아니면 sum[i]=1+sum[자식]의 합 입니다.
toggle[i]는 i가 열려있는지 닫혀있는지 확인합니다.

트리형식으로 생각합시다. 루트노드는 1번 노드입니다.
맨 처음 sum[1]은 1+1의 자식 개수입니다. 이때 cursor의 범위는 2<=cursor<=sum[1]입니다.

find(node,num)은 node번 파일부터 밑으로 num번째 파일을 찾습니다. num==0이면 find(node,num)=node가 됩니다.
change(node,update)는 node==update일때 실행이 되는데 update번 노드의 toggle값을 바꿔주는 역할을 합니다.

move 쿼리가 나오면 cursor+=x를 해주고 범위를 맞춰줍니다. 그리고 find를 해줍시다.
toggle 쿼리가 나오면 change와 find를 해주면 됩니다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

ll sum[2020] = { 0 };
vector <ll> v[2020];
bool toggle[2020] = { 0 };

ll find(ll node, ll num)
{
    if (num == 0) return node;
    for (ll x : v[node])
    {
        if (num <= sum[x]) return find(x, num - 1);
        num -= sum[x];
    }
}
void change(ll node, ll update)
{
    if (node == update)
    {
        if (toggle[node] == false)
        {
            toggle[node] = true;
            for (ll x : v[node])
                sum[node] += sum[x];
        }
        else
        {
            toggle[node] = false;
            for (ll x : v[node])
                sum[node] -= sum[x];
        }
        return;
    }
    
    if (toggle[node] == false) return;
    sum[node] = 1;
    for (ll x : v[node])
    {
        change(x, update);
        sum[node] += sum[x];
    }
    return;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, Q, i, j, M, cursor = 1, x;

    cin >> N >> Q;
    for (i = 1; i <= N; i++)
    {
        sum[i] = 1;
        cin >> M;
        for (j = 0; j < M; j++)
        {
            cin >> x;
            v[i].push_back(x);
        }
    }
    change(1, 1);

    for (i = 0; i < Q; i++)
    {
        string s;
        cin >> s;
        if (s == "move")
        {
            cin >> x;
            cursor += x;
            cursor = min(cursor, sum[1] - 1);
            cursor = max(cursor, (ll)(1));
            cout << find(1, cursor) << "\n";
        }
        else
        {
            change(1, find(1, cursor));
        }
    }
}

감사합니다.