[백준] 10830 : 행렬 제곱 JAVA 풀이

 

import java.io.*;
import java.util.*;
public class Main {
	static int N;
	static int[][] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
        // N과 B를 입력받음
		N = Integer.parseInt(st.nextToken());
		long B = Long.parseLong(st.nextToken());
		
        // 행렬의 값을 저장할 배열 생성
		arr = new int[N][N];
		
        // 배열에 행렬의 값을 저장
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			for(int j=0;j<N;j++) {
            // B가 1인 경우
            // 함수내에서 %1000이 실행되지 않는 것을 해결하기 위해
            // 입력받을 때 %1000을 한 값을 배열에 저장함
				arr[i][j] = Integer.parseInt(st.nextToken())%1000;
			}
		}
		
        // arr행렬을 B제곱하고 %1000한 값을 result에 저장
		int[][] result = pow(arr, B);
		
		StringBuilder sb = new StringBuilder();
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				sb.append(result[i][j]).append(" ");
			}
			sb.append('\n');
		}
		System.out.println(sb);
		
	}
	
	static int[][] pow(int[][] src, long b){
		
        // b가 1이면 src를 그대로 반환
		if(b==1) {
			return src;
		}
        
        // b가 1이 아닌 경우 
		int[][] tmp = new int[N][N];
        
        // b를 반으로 분할해서 재귀
		tmp = pow(src, b/2);
        
		// b/2제곱한 것끼리 곱해서 merge함
		tmp = multiply(tmp, tmp);
		
        // b가 홀수라면 한 번 더 곱해줌
		if(b%2==1) {
			tmp = multiply(tmp, arr);
		}
		
		return tmp;
	}
	// 행렬끼리 곱하는 함수
	static int[][] multiply(int[][] A, int[][] B){
		
		int[][] tmp = new int[N][N];
		
        // 행렬의 곱을 구하고 %1000한 값을 저장해서 반환
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				for(int k=0;k<N;k++) {
					tmp[i][j] += A[i][k]*B[k][j];
					tmp[i][j] %= 1000;
				}
			}
		}
		return tmp;
	}
	

}