희소 배열

모든 정점의 나가는 간선이 한개인 유향 그래프를 생각하자.

특정 노드 N에서 K번 이동한 노드를 찾는 경우, 시작노드부터 K번 단순 이동하게 된다면 O(K)가 걸린다는 것을 알 수 있다. 선형시간이므로 K가 큰 수가 들어오게 된다면 계산이 어려워진다.

하지만 항상 어떤 노드는 다른 노드 하나와 연결되어 있기 때문에 K번째 노드는 K-1번째 노드 다음이라는 것을 알 수 있다.
이를 다시생각해본다면
K+2번째 노드는 (K+1) + 1번 이동
K+4번째 노드는 (K+2) + 2번 이동
K+8번째 노드는 (K+4) + 4번 이동
과 같이 나타낼 수 있다. 즉, 이전 이동정보를 저장해서 추후에 사용할 수 있다는 것 이다.
시작 노드 N, 이동횟수 K를 저장한 배열 arr[N][K]가 있다고 생각해면
N에서 2번 이동한 경우는 arr[N][2]가 되고, 이를 다시 나타내면 arr[arr[N][1]][1]이 된다. N에서 8번 이동한 경우를 가정하면, arr[arr[N][4]][4]가 되는 것도 마찬가지다.

이를 통해 생각할수 있는 것은, 시작 노드의 정보와 이동 횟수의 정보를 이차원 배열로 저장해서 계산횟수를 줄일 수 있다는 것 이다. 이동정보 K를 logK만큼 저장하면, 우리는 1, 2, 4 ~~ K -> 1, 2, 3 ~~ logK로 나타낼 수 있다. 이 정보를 통해 K를 이진수로 나타내보면, 예를들어 K가 13인 경우 1101이 된다. 그렇다면 시작점으로부터 8번가고, 4번가고, 1번가는 경우와 같다는 것 이다. 그러므로 탐색 시간이 O(logK)로 줄어들게 된다.

문제

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

전사함수를 만족하므로 특정 노드 i에서 항상 밖으로 나가는 간선 하나만을 만족한다.

그러므로 위의 설명과 같이 배열을 통한 정보 저장으로 해결할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
int m, funcarr[21][200001], Q;
int main(){
    fastio;
    cin>>m;
    for(int i=1; i<=m; i++)
        cin>>funcarr[0][i];
    for(int i=1; i<=20; i++){
        for(int j=1; j<=m; j++){
            funcarr[i][j] = funcarr[i-1][funcarr[i-1][j]];
        }
    }
    cin>>Q;
    while(Q--){
        int n, x; cin>>n>>x;
        for(int i=20; i>=0; i--){
            if(n >= 1 << i){
                n -= 1 << i;
                x = funcarr[i][x];
            }
        }
        cout<<x<<'\n';
    }
}