[백준] 2099번 The game of death

[적용한 알고리즘]

(굳이 꼽자면) 그래프, 행렬

 

[아이디어]

요약하면, A->B 까지 정확히 K번 거쳐서 갈 수 있느냐는 말이다.

행렬의 거듭제곱을 이용하면 구할 수 있다고 한다.

"행렬 A^k 에서 (i, j) 의 의미가 결국  i->j 까지 k 번만에 갈 수 있느냐?" 이므로,

행렬 거듭제곱 알고리즘만 짜면 된다.

 

[교훈]

내용

 

<코드>

#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<bool>> matrix;

matrix operator * (const matrix &a, const matrix &b){
    int n = a.size();
    matrix c(n, vector<bool>(n));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            for (int k = 0; k < n; k++){
                if (a[i][k] & b[k][j]){
                    c[i][j] = true;
                }
            }
        }
    }

    return c;
}

matrix pow(matrix a, int M){
    int N = a.size();
    matrix ans(N, vector<bool>(N));

    for (int i = 0; i < N; i++) ans[i][i] = true;

    while (M > 0){
        if (M % 2 == 1){
            ans = ans * a;
        }
        a = a * a;
        M /= 2;
    }
    return ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K, M;
    cin >> N >> K >> M;
    matrix Game(N, vector<bool>(N));

    for (int i = 0; i < N; i++){
        int x, y;
        cin >> x >> y;
        Game[i][x - 1] = true;
        Game[i][y - 1] = true;
    }

    matrix ans = pow(Game, K);

    while (M--){
        int x, y;
        cin >> x >> y;

        printf("%s\n", ans[x - 1][y - 1] ? "death" : "life");
    }
    return 0;
}