[programmers][2020카카오공채] 자물쇠와 열쇠

문제 : https://programmers.co.kr/learn/courses/30/lessons/60059#

---

N, M 범위가 20으로 널널하기 때문에 구현, 시뮬레이션으로 풀었다.

일단 키를 회전한 모습을 배열에 저장한다.

for (int i = 0; i<M; i++) {
	for (int j = 0; j<M; j++) {
		keys[0][i][j] = key[i][j]; // 0
		keys[1][j][M - 1 - i] = key[i][j]; // 90
		keys[2][M - 1 - i][M - 1 - j] = key[i][j]; // 180
		keys[3][M - 1 - j][i] = key[i][j]; //270
	}
}

keys 0, 1, 2, 3 인덱스에 key를 시계방향으로 0, 90, 180, 270 도 회전한 모습을 넣었다.

그리고 lock배열의 홈의 개수를 센다.

for (int x = -M; x<N; x++) {
	for (int y = -M; y<N; y++) {
		for (int d = 0; d<4; d++) {
			if (check(x, y, keys[d], lock) == emptyCnt)
            	return true;
		}
	}
}

반복문의 x, y는 key의 시작위치(왼쪽 위 인덱스) 를 뜻한다. 자물쇠 영역을 벗어날수도 있기 때문에 시작인덱스는 행, 열 모두 -M부터이다.

check 함수는 lock배열의 x, y를 시작위치로 두고 keys[d] 모양의 키를 넣었을 때 열쇠와 자물쇠의 돌기가 만나는지 체크한다. 만난다면 불가능한 경우로 -1을 반환하고 만나지 않고 열쇠가 잘 들어갔다면 이 때 사용된 열쇠의 돌기 개수를 반환한다. 반환된 열쇠의 돌기 개수가 자물쇠의 홈 개수와 같다면 정답이 가능한 경우이다.

 

시간복잡도는 key의 시작위치를 정하는데 O((N+M)^2)가 소요되고 그 위치에서 자물쇠가 맞아떨어지는지 체크하는데 O(M^2)가 소요되므로 O((N+M)^2 * M^2)가 된다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/2020%EC%B9%B4%EC%B9%B4%EC%98%A4%EA%B3%B5%EC%B1%84/%EC%9E%90%EB%AC%BC%EC%87%A0%EC%99%80%20%EC%97%B4%EC%87%A0.cpp