[백준] 3117 - YouTube

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

3117번: YouTube

 

많이 봐왔던 sparse matrix 문제이다. 희소 배열에 대한 개념이 없다면 여기를 참고해도 좋다.

이 문제의 입력으로 사이클이 생기는 그래프가 주어질 수 있다. 그래서 M의 범위가 10억이어도 상관이 없는 것이고, M의 범위가 10억 인 만큼 sparse matrix를 다음과 같이 정의할 것이다.

p[i][j] = 정점 i의 2^j 번째 부모, j는 최소 31(2^30 = 10억 이상)

 

처음 K개의 입력으로 p[i][0]을 채워 넣을 수 있을 것이다.

memset(p, -1, sizeof(p));
for (int i = 1; i <= k; i++) {
    cin >> p[i][0];
}

 

다음은 p[i][0]의 정보를 바탕으로 p[i][1] ~ p[i][30]의 정보를 채워 넣을 수 있을 것이다.

for (int i = 1; i <= 30; i++) {
    for (int j = 1; j <= k; j++) {
        if (p[p[j][i - 1]][i - 1] != -1) {
            p[j][i] = p[p[j][i - 1]][i - 1];
        }
    }
}

 

다음은 M분에 시청하는 동영상 번호를 출력하면 되는데, 주의해야 할 점은 여기서 1분에 시청하는 동영상은 추천 동영상이 아니라 맨 처음 시청하는 동영상인 것이다.

따라서 우리가 구해야 할 것은 맨 처음 시청하는 동영상의 m - 1번째 부모이다.

#include <iostream>
#include <cstring>
using namespace std;

int n, k, m;
int p[100001][31], inp[100001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> m;

    for (int i = 1; i <= n; i++) {
        cin >> inp[i];
    }

    memset(p, -1, sizeof(p));
    for (int i = 1; i <= k; i++) {
        cin >> p[i][0];
    }

    for (int i = 1; i <= 30; i++) {
        for (int j = 1; j <= k; j++) {
            if (p[p[j][i - 1]][i - 1] != -1) {
                p[j][i] = p[p[j][i - 1]][i - 1];
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        int target = m - 1;
        while (target) {
            for (int j = 30; j >= 0; j--) {
                if (target >= (1 << j)) {
                    inp[i] = p[inp[i]][j];
                    target -= (1 << j);
                    break;
                }
            }
        }
        cout << inp[i] << ' ';
    }
}