[시뮬레이션] N진수 암호화를 사용한 방향 조합 + 행렬 회전

시뮬레이션 문제를 풀다가, 상당히 기발한 방법을 새로 공부했다.

BOJ15683 - 감시

BOJ18808 - 스티커 붙이기

BOJ12100 - 2048

 

1. 4가지 방향에 대한 모든 가능한 조합 (중복 순열) 쉽게 구하기

CCTV가 N E S W 4가지 방향을 감시한다고 하자.

8개의 CCTV가 있을때, 각 CCTV가 어느 방향을 감시하는지 모든 경우의 수를 구하고자 한다면, 4가지 방향을 중복으로 뽑아 순열로 나열하는 경우를 모두 구하면 된다.

 

일반적으로 백트래킹을 이용해 중복 순열을 구현할 수 있으나 (BOJ 15651 - N과 M (3)), 

4진수 숫자를 이용해서 아주 쉽게 중복 순열의 모든 경우의 수를 구할 수 있다.

 

Encryption

N E S W 이렇게 총 4가지 방향이므로 4진수를 사용,

CCTV가 총 8개이므로 8자리 4진수를 사용한다.

 

4진수 수 각 자릿수가 바로 각 CCTV의 방향을 의미한다.

 

Decryption

4진수 수를 총 8번 4로 나누는데, 나눌때마다 나오는 나머지가 맨 아래 자릿수에 해당하는 숫자가 된다.

int cctv_cnt = 8; // CCTV 8개
FOR(quad, 0, 1 << (2 * cctv_cnt)) { // 8자리 4진수를 모두 탐색; 4^8
  int tmp = quad;

  // For each cctv
  FOR(i, 0, cctv_cnt) {            
    int dir = tmp % 4; // 현재 4진수 맨 아래 자리의 숫자; i번째 CCTV의 방향
    tmp /= 4;
    ...
  }
}

 

 

뽑을 수 있는 가짓수가 4가지가 아니라 더 많거나 작아도, N진수 개념을 쓰면 쉽게 암호화/복호화 가능

 

2. 행렬 회전

행렬 회전은, 회전시킬 행렬 A의 좌표들과, 회전 시킨 후의 행렬 B의 좌표들을 비교하며 규칙을 찾는 방법이 잘 먹힌다.

 

- 직사각행렬의 회전

for (int i = 0; i < r; i++)
	for (int j = 0; j < c; j++)
		arr[j][r - 1 - i] = tmp[i][j]; // Clockwise

 

- 정사각행렬의 회전

정사각행렬은 직사각행렬의 집합에 포함되므로, 직사각행렬 식과 동일함을 볼 수 있다.

 

위 식을 이용한 직사각행렬 90도 회전 코드

template<typename T>
void rec_rotate90(vector<vector<T>> & arr) {
	assert(arr.size()); // arr shouldn't be empty

	// Assume r,c are global variable (swapped at the end)
	// int r = arr.size(), c = arr[0].size();

	vector<vector<T>> tmp(r, vector<T>(c));

	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			tmp[i][j] = arr[i][j];

	// (For rectangle) Resizing the original array : O((c+1)*|r-c|)
	arr.resize(c, vector<T>(r));
	for (auto& col : arr)
		col.resize(r);

	// Rotate tmp into arr
	for (int x = 0; x < r; x++)
		for (int y = 0; y < c; y++)
			arr[y][r-1-x] = tmp[x][y]; // Clockwise
			//arr[c-1-y][x] = tmp[x][y]; // Counter-Clockwise

	swap(r, c); // when rotating rectangle
}

def rotate_a_matrix_by_90_degree(a):
    n = len(a) # 행 길이 계산
    m = len(a[0]) # 열 길이 계산
    result = [[0] * n for _ in range(m)] # 결과 리스트
    for i in range(n):
        for j in range(m):
            result[j][n - i - 1] = a[i][j]
    return result