[PS] BOJ_1780

BOJ_1780

💡 생각하자

먼저, 주어진 행렬이 같은 수로 이루어졌는지 판별하는 함수를 만든다.

위의 함수를 재귀적으로 수행할 때, 전달되는 행렬이 분할된 9개 중 어떤 것인지 알려줘야한다. 그러므로 해당 행렬의 첫번째 원소의 좌표를 전달한다.

💻 구현하자

• 주어진 행렬이 같은 수로 이루어졌는지 판별하는 함수

int check(int n, int s_row, int s_col) { // n by n matrix
	int temp = mat[s_row][s_col];

	for (int i = s_row;i < s_row + n;i++) {
		for (int j = s_col;j < s_col + n;j++) {
			if (temp != mat[i][j]) return FALSE;
		}
	}
	count(temp); // all number is same!

	return TRUE;
}

- s_row, s_col: 주어진 행렬의 첫번째 원소 좌표

행렬을 돌면서 첫번째 원소(temp)와 비교한다.
-> 다른 값의 원소가 발견되면 FALSE
-> 반복문을 끝까지 수행하면 모두 같은 수로 이루어졌음을 의미한다. 그러므로 TRUE

- count()는 temp로만 이루어진 행렬의 수를 세는 함수

• 행렬을 분할하는 함수

void divideMat(int n, int start_row, int start_col) {
	int res = check(n, start_row, start_col);
	if ( n > 1 && res == FALSE) { // exit condition!
		for (int i = start_row;i < start_row + n;i += n / 3) { // divide to 9 matrices
			for (int j = start_col;j < start_col + n;j += n / 3){
				divideMat(n / 3, i, j);
			}
		}
	}
}

- 종료조건: 1 by 1 행렬이 되거나 해당 행렬이 모두 같은 수로 이루어져 있을 경우, 더이상 분할할 필요가 없어진다.

• 초기 호출문

divideMat(n, 0, 0);   

💥 발전하자

• 개선점

1. 나의 코드는 19784KB 메모리 / 532ms 사용했는데, 다른 사람을 보니 같은 C언어로 6812KB / 96ms 였다. 하지만 그 코드를 이해하기가 어려웠다. (비트연산을 사용한 것 같은데..)

📌 참고하자

나의 코드(Github)
엄청난 고수의 코드