[BaekJoon] 2099 The game of death (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int participantNum;
    static int maxTurnNum;
    static int gameNum;

    static int[][] relations; // relations[i][j] = (i + 1)번 사람이 (j + 1)번 사람을 가리키고 있는지 여부
    static int[][] games;

    static void input() {
        Reader scanner = new Reader();

        participantNum = scanner.nextInt();
        maxTurnNum = scanner.nextInt();
        gameNum = scanner.nextInt();
        relations = new int[participantNum][participantNum];
        games = new int[gameNum][2];

        for(int idx = 0; idx < participantNum; idx++) {
            int person1 = scanner.nextInt() - 1;
            int person2 = scanner.nextInt() - 1;

            relations[idx][person1] = relations[idx][person2] = 1;
        }

        for(int idx = 0; idx < gameNum; idx++) {
            games[idx][0] = scanner.nextInt() - 1;
            games[idx][1] = scanner.nextInt() - 1;
        }
    }

    static void solution() {
        // k번째 지목될 수 있는 사람들의 경우를 구한다
        int[][] finalRelations = findFinalRelations(relations, maxTurnNum);

        // 궁금한 두 명의 사람에 대해 a번 사람이 시작해서 b번 사람이 k번째에 걸리는 경우가 있는지 확인하고 그에 맞게 출력한다
        StringBuilder sb = new StringBuilder();
        for(int idx = 0; idx < gameNum; idx++) {
            sb.append(finalRelations[games[idx][0]][games[idx][1]] == 0 ? "life" : "death").append('\n');
        }

        System.out.print(sb);
    }
    
    // 가리킨 정보에 해당하는 2차원 배열 relations를 이용하여 아래와 같이 k번째 지목될 수 있는 사람들의 경우를 구한다
    //  - relations * relations = relations2 -> 2번째 지목될 수 있는 사람들의 경우
    //  - relations2 * relations2 = relations4 -> 4번째 지목될 수 있는 사람들의 경우
    //  - relations2 * relations = relations3 -> 3번째 지목될 수 있는 사람들의 경우
    //  -> 이렇게 분할 정복을 통해 k번째의 2차원 배열을 구한다
    static int[][] findFinalRelations(int[][] relations, int gameNum) {
        if(gameNum == 1) {
            return relations;
        }

        int[][] temp = findFinalRelations(relations, gameNum / 2);
        int[][] result = multiplyMatrix(temp, temp);
        if(gameNum % 2 == 1) {
            result = multiplyMatrix(result, relations);
        }
        return result;
    }

    static int[][] multiplyMatrix(int[][] mat1, int[][] mat2) {
        int[][] result = new int[mat1.length][mat1[0].length];

        for(int row = 0; row < participantNum; row++) {
            for(int col = 0; col < participantNum; col++) {
                int sum = 0;
                for(int idx = 0; idx < participantNum; idx++) {
                    sum += (mat1[row][idx] * mat2[idx][col]);
                }

                if(sum != 0) {
                    result[row][col] = 1;
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}