[BaekJoon] 12916 K-Path (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static final int DIVISOR = 1_000_000_007;

    static int villageCount;
    static int targetDistance;
    static int[][] connectivity;

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

        villageCount = scanner.nextInt();
        targetDistance = scanner.nextInt();
        connectivity = new int[villageCount][villageCount];

        for (int row = 0; row < villageCount; row++) {
            for (int col = 0; col < villageCount; col++) {
                connectivity[row][col] = scanner.nextInt();
            }
        }
    }

    /*
     * 문제에서 길의 길이는 1로 통일한다고 하였으니, 길이가 K인 경로는 K번 움직인 이후의 경로를 의미한다
     * K번 움직인 이후의 각 마을부터 다른 모든 마을까지 경로의 경우의 수를 구하려면 주어진 인접행렬을 K번 곱하면 된다
     * 그러나 단순 반복문으로 곱하기에는 K의 최대값이 1_000_000_000이기 때문에 시간초과가 발생한다
     * 그러므로 거듭제곱을 이용하여 주어진 인접행렬을 K번 곱한 후의 행렬을 구한다
     */
    static void solution() {
        int[][] numberOfWay = findNumberOfWay(targetDistance, connectivity);
        System.out.println(findAllNumberOfWayInKthDistance(numberOfWay));
    }

    static int findAllNumberOfWayInKthDistance(int[][] numberOfWay) {
        int answer = 0;
        for (int row = 0; row < villageCount; row++) {
            for (int col = 0; col < villageCount; col++) {
                answer += numberOfWay[row][col];
                answer %= DIVISOR;
            }
        }

        return answer;
    }

    static int[][] findNumberOfWay(int exponent, int[][] matrix) {
        if (exponent == 1) {
            return matrix;
        }

        int[][] temp = findNumberOfWay(exponent / 2, matrix);
        int[][] result = multiplyMatrix(temp, temp);
        if (exponent % 2 == 1) {
            result = multiplyMatrix(result, matrix);
        }
        return result;
    }

    static int[][] multiplyMatrix(int[][] matrix1, int[][] matrix2) {
        int[][] result = new int[villageCount][villageCount];

        for (int row = 0; row < villageCount; row++) {
            for (int col = 0; col < villageCount; col++) {
                for (int idx = 0; idx < villageCount; idx++) {
                    long temp = (long) matrix1[row][idx] * matrix2[idx][col];
                    result[row][col] += (int) (temp % DIVISOR);
                    result[row][col] %= DIVISOR;
                }
            }
        }

        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());
        }
    }
}