[BaekJoon] 10830 행렬 제곱 (Java)

1.  문제 링크

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

2.  문제

요약

• 크기가 N x N인 행렬 A가 주어집니다.
• 이 때, A의 B제곱을 구하는 문제입니다.
• 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력합니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 5보다 작거나 같은 행렬의 크기 N과 1보다 크거나 같고 100,000,000,000보다 작거나 같은 B가 주어지고 두 번째 줄부터 N개의 줄에는 행렬의 각 원소가 주어집니다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0입니다.
• 출력: 첫 번째 줄부터 N개의 줄에 걸쳐 행렬 A를 B 제곱한 결과를 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static long B;
	static int[][] matrix;
	static int N;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		B = scanner.nextLong();
		matrix = new int[N][N];
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < N; col++)
				matrix[row][col] = scanner.nextInt();
		}
	}
	
	static void solution() {
		int[][] result = powMatrix(matrix, B);
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < N; col++) {
				sb.append(result[row][col] % 1000).append(' ');
			}
			sb.append('\n');
		}
		System.out.println(sb);
	}
	
	static int[][] powMatrix(int[][] mat, long involution) {
		if(involution == 1)
			return mat;
		else {
			int[][] temp = powMatrix(mat, involution / 2);
			if(involution % 2 == 0)
				return mulMatrix(temp, temp);
			else
				return mulMatrix(mulMatrix(temp, temp), mat);
		}
	}
	
	static int[][] mulMatrix(int[][] mat1, int[][] mat2) {
		int[][] result = new int[N][N];
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < N; col++) {
				int temp = 0;
				for(int index = 0; index < N; index++)
					temp += ((mat1[row][index] * mat2[index][col]) % 1000);
				result[row][col] = temp;
			}
		}
		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());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
}