[백준] 10830번 : 행렬 제곱 - JAVA [자바]

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

10830번: 행렬 제곱

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

이 번 문제는 이전에 분할정복 카테고리에서 풀었었던 1629번 : 곱셈 문제를 풀어보았다면 그리 어려운 문제는 아니다.

 

만약 풀어보지 않으셨다면 위 문제부터 풀고 오신다면 수월하게 이 문제도 풀 수 있으니 한 번 보고오시는 것을 추천드린다.

 

 

 

위 곱셈문제 풀이와 같게 행렬의 지수(exponential)를 절반으로 잘라가면서 분할정복을 해주면 된다.

 

 

좀 더 자세하게 말하자면 다음과 같다.

M을 행렬(Matrix)라고 할 떄, 아래와 같이 분할하여 연산 할 수 있다.

 

 

 

 

 

만약 지수가 홀수일 경우 다음과 같이 연산하면 된다.

 

 

 

 

 

위를 그림으로 표현하자면 다음과 같다.

 

 

 

즉, 앞서 언급했던 곱셈 문제 원리랑 같은 방식으로 접근하면서 두 행렬을 곱셈해주는 메소드만 구현을 해주면 끝난다.

 

 

 

단, 주의할 것이 있다. B의 입력범위를 보면 1 ≤ B ≤ 100,000,000,000 (천억) 이다. 이는 int형을 넘기 때문에 long 타입으로 받아야 하며, 문제 조건을 보면 '각 원소를 1000으로 나눈 나머지'로 출력해야한다.

 

이 점만 유의하여 작성하면 별다른 문제 없이 통과할 수 있을 것이다. (자세한 코드는 아래 풀이에서 주석으로 설명해주겠다.)

 

 

 

 

 

 

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

 

가장 기본적인 재귀 방식으로 Scanner와 BufferedReader을 이용하여 풀어볼 것이다. 그리고 마지막으로 반복문을 이용한 풀이 방식도 보여주고자 한다.

이번에는 출력은 모두 StringBuilder 로 통일하여 입력방법만 달리하여 풀이하겠다.

 

1. 재귀 + Scanner

2. 재귀 + BufferedReader

3. 반복문 + BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [재귀 + Scanner]

 

import java.util.Scanner;

public class Main {

	final static int MOD = 1000;
	public static int N;
	public static int[][] origin;	// A^1 일 때의 배열(초기 배열)
	
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
				
		N = in.nextInt();
		long B = in.nextLong();	// 타입 주의
		
		origin = new int[N][N];
		
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				
				/*
				 * B=1 일 때는 pow과정에서 바로 A가 반환 될 수 있다.
				 * 이 때의 경우 만약 원소가 1000이상일 경우 pow메소드에서 모듈러연산이
				 * 실행되지 않기 때문에 오답이 되어버린다.
				 * 
				 * 이를 방지하기 위해 초기 행렬에도 1000으로 나눈 나머지 값으로
				 * 초기화를 해준다.
				 */
				origin[i][j] = in.nextInt() % MOD;
			}			
		}
		
		int[][] result = pow(origin, 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);
		
	}


	// 행렬 제곱 분할정복 메소드
	public static int[][] pow(int[][] A, long exp) {

		// 지수가 1일 땐 A를 return한다.
		if(exp == 1L) {
			return A;
		}
		
		// 지수를 절반으로 분할하여 재귀호출
		int[][] ret = pow(A, exp / 2);
		
		// 하위 재귀에서 얻은 행렬을 제곱해준다.
		ret = multiply(ret, ret);
		
		// 만약 지수가 홀수라면 마지막에  A^1 (origin)을 곱해준다.
		if(exp % 2 == 1L) {
			ret = multiply(ret, origin);
		}
		
		return ret;
	}
	
	
	// o1과 o2 행렬을 곱해주는 메소드
	public static int[][] multiply(int[][] o1, int[][] o2) {
		
		int[][] ret = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				for(int k = 0; k < N; k++) {
					
					ret[i][j] += o1[i][k] * o2[k][j];
					ret[i][j] %= MOD;	// 행렬 원소 연산이 끝나면 MOD로 나머지연산
				}
			}
		}
		return ret;
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

여기서 주의할 점은, 분할정복 메소드인 pow()를 자세히 보면 if(exp == 1) 일 때 return A를 하도록 되어있다.

 

 

만약에 행렬이 다음과 같이 주어졌다고 가정해보자. (입력 받을 때 행렬의 원소는 최대 1000까지 받을 수 있음)

 

 

1000 1000 1000

1000 1000 1000

1000 1000 1000

 

 

그리고 B가 1로 주어졌다면, 출력이 어떻게 될까? 분명히 각 원소를 1000으로 나눈 행렬이 출력이 되어야 하기 때문에 다음과 같이 출력해야한다.

0 0 0

0 0 0

0 0 0

 

하지만, pow메소드를 보면 exp==1 일 때 A를 그대로 return하기 때문에 모듈러 연산이 적용되지 않는다.

즉, 다음과 같이 그대로 출력이 되어버린다.

 

1000 1000 1000

1000 1000 1000

1000 1000 1000

 

그렇기 때문에 해결 방법은 여러가지가 있지만, 가장 간단한 방법으로는 맨 처음 입력 받을 때 미리 1000으로 나눈 나머지 값으로 초기화를 해주는 것이다. 그러면 모듈러 연산 법칙에도 벗어나지 않으면서 제대로 된 값을 출력해줄 수 있다.

 

 

 

---

- 방법 2 : [재귀 + BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

풀이 방법 자체는 달라진 것은 없다.

 

 

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

public class Main {

	final static int MOD = 1000;
	public static int N;
	public static int[][] origin;	// A^1 일 때의 배열(초기 배열)
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				
		N = Integer.parseInt(st.nextToken());
		long B = Long.parseLong(st.nextToken());	// 타입 주의
		
		origin = 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 일 때는 pow과정에서 바로 A가 반환 될 수 있다.
				 * 이 때의 경우 만약 원소가 1000이상일 경우 pow메소드에서 모듈러연산이
				 * 실행되지 않기 때문에 오답이 되어버린다.
				 * 
				 * 이를 방지하기 위해 초기 행렬에도 1000으로 나눈 나머지 값으로
				 * 초기화를 해준다.
				 */
				origin[i][j] = Integer.parseInt(st.nextToken()) % MOD;
			}			
		}
		
		int[][] result = pow(origin, 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);
		
	}


	// 행렬 제곱 분할정복 메소드
	public static int[][] pow(int[][] A, long exp) {

		// 지수가 1일 땐 A를 return한다.
		if(exp == 1L) {
			return A;
		}
		
		// 지수를 절반으로 분할하여 재귀호출
		int[][] ret = pow(A, exp / 2);
		
		// 하위 재귀에서 얻은 행렬을 제곱해준다.
		ret = multiply(ret, ret);
		
		// 만약 지수가 홀수라면 마지막에  A^1 (origin)을 곱해준다.
		if(exp % 2 == 1L) {
			ret = multiply(ret, origin);
		}
		
		return ret;
	}
	
	
	// o1과 o2 행렬을 곱해주는 메소드
	public static int[][] multiply(int[][] o1, int[][] o2) {
		
		int[][] ret = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				for(int k = 0; k < N; k++) {
					
					ret[i][j] += o1[i][k] * o2[k][j];
					ret[i][j] %= MOD;	// 행렬 원소 연산이 끝나면 MOD로 나머지연산
				}
			}
		}
		return ret;
	}
}

 

 

 

크게 어려울 것은 없을 것이다.

만약에 여러분이 메모리 행렬 곱셈을 좀 더 효율 좋게 만들고 싶다면 행렬 곱셈 부분에 대해 캐싱을 이해한다면 다음과 같이 변형할 수 있다.

 

[수정 전 : 일반적인 행렬 곱셈 방식]

public static int[][] multiply(int[][] o1, int[][] o2) {
	
	int[][] ret = new int[N][N];
	
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			for(int k = 0; k < N; k++) {
				
				ret[i][j] += o1[i][k] * o2[k][j];
				ret[i][j] %= MOD;	// 행렬 원소 연산이 끝나면 MOD로 나머지연산
			}
		}
	}
	return ret;
}

 

 

 

[수정 후 : 효율적인 캐싱을 위한 행렬 곱셈 방식]

public static int[][] multiply(int[][] o1, int[][] o2) {
		
	int[][] ret = new int[N][N];
		
	int r;
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
				
			// o1(ik) 원소를 고정시켜두고, 그에 대한 o2의 k열을 고정시켜 j행을 움직이면서 연산한다.
			r = o1[i][k];			
			for (int j = 0; j < N; j++) {
				ret[i][j] += r * o2[k][j];
				ret[i][j] %= MOD;
			}
		}
	}
	return ret;
}

 

 

한 번 직접 테스트 해보셔도 좋을 것 같다.

 

 

---

- 방법 3 : [반복문 + BufferedReader]

 

 

 

재귀로 풀이하는 대신 반복문으로 제곱해나가면서 풀이하는 방식이다.

살짝 어려울 수 있지만, 재귀로 풀이했을 때의 과정을 거꾸로 풀이하면 된다.

 

 

조금 설명을 덧붙이자면, 반복문은 B가 0보다 클 때 반복하면서 B를 매 회마다 2로 나누면서 진행한다. 그리고 그 안에서 origin 행렬(A)의 경우 매 회마다 origin의 '제곱 행렬'으로 갱신을 해준다.

 

그리고 출력을 할 배열인 result는 B가 홀 수일 때만 origin의 배열과 자기 자신을 곱한 행렬로 갱신을 해주면 된다.

말로 이해하기는 어려울 수 있으니 일단, 코드를 보면서 주석을 통해 최대한 이해해보도록 하자.

 

다만 결과값을 담을 result 배열을 단위행렬로 만들고 시작해야하는 점 하나만 추가하면 된다.

 

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

public class Main {
	
	final static int MOD = 1000;
	public static int N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(st.nextToken());
		
		int[][] origin = new int[N][N];
		int[][] result = new int[N][N];
		
		long B = Long.parseLong(st.nextToken());	

		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < N; j++) {
				origin[i][j] = Integer.parseInt(st.nextToken());
			}
			// 결과값을 담을 행렬 (맨 처음 초기값은 단위행렬(I)로 초기화를 해준다.)
			result[i][i] = 1;
		}
		
		
		/*
		 * origin 행렬은 이전 loop에서 제곱값을 갖고있는 행렬이고,
		 * result는 지수가 홀 수 일 때, 이전 loop에서 얻은 제곱 행렬인 origin과
		 * 현재 result 행렬을 곱해주는 방식으로 간다.
		 * 
		 * 즉, 재귀 과정을 역순으로 거치면 된다.
		 * 
		 * ex)
		 * A^11 과정일 떄,
		 * 
		 * B = 11 (B % 2 == 1) -> I * A^1 = A^1 (result)
		 *                     -> A^1 * A^1 = A^2 (origin)
		 *                     
		 * B = 5  (B % 2 == 1) -> A^1 * A^2 = A^3 (result)
		 *                     -> A^2 * A^2 = A^4 (origin)
		 *                     
		 * B = 2  (B % 2 == 0) -> A^4 * A^4 = A^8 (origin)
		 *
		 * B = 1  (B % 2 == 1) -> A^3 * A^8 = A^11 (result)
		 *                     -> A^8 * A^8 = A^16 (origin)  
		 */
		while(B > 0) {
			
			// 지수가 홀수라면 origin 배열을 한 번 더 곱해준다.
			if(B % 2 == 1) {	// b % 2 == 1 을 (b & 1L) != 0L 으로도 수정할 수 있다.
				result = multiply(result, origin);
			}
			origin = multiply(origin, origin);
			
			B /= 2;
		}
		
		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);
	}
	
	
	public static int[][] multiply(int[][] o1, int[][] o2) {
		
		int[][] ret = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				for(int k = 0; k < N; k++) {
					
					ret[i][j] += o1[i][k] * o2[k][j];
					ret[i][j] %= MOD;
				}
			}
		}
		return ret;
	}
	
}

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

채점 번호 : 29540076  -  방법 3 : 반복문 + BufferedReader

채점 번호 : 29540070  -  방법 2 : 재귀 + BufferedReader

 

채점 번호 : 29540065  -  방법 1 : 재귀 + Scanner

 

 

 

지수가 큰 것에 비해 시간차이가 크지는 않은 것 같다. (생각해보면 1000억이면 대략 재귀가 깊더라도 37까지밖에 안가긴 한다.)

 

---

• 정리

 

이 번 문제는 이전의 곱셈 문제와 겹치는(행렬을 곱해준다는 것만 바뀐) 문제라서 크게 어려운 점은 없었을 것이다. 다만 주의해야 할 점은 모듈러 연산과 예외처리정도? 이었을 것이다.

 

혹여 어렵거나 이해가 가지 않는다면 언제든 댓글로 남겨주시기 바란다. 최대한 빠른 시일 내로 답변드리도록 노력하겠다.