[백준] 2099 The game of death

더 게임 오브 데.. 스.. 어렵다...

K개 간선을 지나서 A->B로 갈 수 있다면 death 아니면 life다.

생각이 안나서 폭풍도움을 받고 A^k을 하고 A[i][j]가 1이라면

i->j라는 사실을 알았따...

생각해보니까 이산수학에서 transitive closure로 나온 것 같다.

길이가 n인 path가 있으려면 A^n해서 확인했었다...!

잘 기억해둬야겠다..

행렬곱 n^3 * K(1,000,000) 이니까 정직하게 곱하면 시간안에 못푼다..!

그래서 A^k를 log만에 구하는 방법으로 구현해야한다!

하지만 내 소스는 결국 틀렸다 ㅎㅎ..60..%..

백준의 코드를 보며 공..부..하고.. 풀었다..!

코드 깨끗하게 잘짜는 연습 해야겠다 ㅎㅎ

소스코드

#include <iostream>
#include <algorithm>
#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] = 1;
            }
        }
    }
    return c;
}
Matrix go(Matrix x, int y) {
    int n = x.size();
    Matrix ans(n, vector<bool>(n));
    //행렬 항등원
    for (int i = 0; i < n; i++) ans[i][i] = 1;
 
    while (y > 0) {
        if (y & 1) ans = ans*x;
        else x = x*x;
        y /= 2;
    }
    return ans;
}
int main() {
    int n, m, k; scanf(" %d %d %d", &n, &k, &m);
    Matrix x(n, vector<bool>(n));
    for (int i = 0; i < n; i++) {
        int a, b; scanf(" %d %d", &a, &b);
        a--; b--;
        x[i][a] = x[i][b] = 1;
    }
    Matrix ans = go(x, k);
    for (int i = 0; i < m; i++) {
        int a, b; scanf(" %d %d", &a, &b);
        a--; b--;
        if (ans[a][b]) puts("death");
        else puts("life");
    }
}