https://school.programmers.co.kr/learn/courses/30/lessons/60059
M x M 크기인 Key를 N x N크기의 Lock에 돌리거나 이동시켜 꼭 들어맞게 할 수 있는지 여부를 확인하는 문제이다.
M과 N 모두 3~20의 작은 범위이므로 모든 케이스를 확인하는 완전탐색을 사용하면 될 것 같다고 생각하였다.
key를 회전하는 것은 아래 그림과 같다.
key를 이동시킨다는 것은 아래 그림과 같다. (범위를 벗어나면 돌기가 사라지며 원래 돌기가 있던 곳은 빈 칸이 된다)
아래 위로 움직이는 경우도 유사하니 따로 첨부하지는 않겠다.
이렇게 key를 조작해 각각의 케이스마다 key를 lock에 끼워 맞춰 lock의 모든 공백이 메워지도록 할 수 있는지 검사해야 한다(돌기끼리 충돌해도 실패)
key의 모든 케이스와 lock을 비교하여 채워질 수 있는지 검사한다.
예시의 첫 번째 key로는 lock의 모든 홈을 메울 수 없어 실패이고
두 번째 key를 사용하면 홈은 메우지만 아래쪽 돌기가 lock의 돌기와 충돌한다.
세 번째 key를 사용하면 lock의 모든 홈을 메울 수 있다.
이 문제는 아이디어는 간단하지만 key를 조작하는 케이스들을 구하는 것, 그리고 key보다 lock이 더 클 수 있어 그에 따라 key를 lock에 대 보는 모든 경우를 나타내야 해서 구현이 까다로운 문제인 것 같다.
key와 lock의 크기가 작은 만큼 이 문제는 속도 면에서 신경쓰는 것을 줄이고 기능 별로 함수를 나누어 구현하기로 하였다.
내가 풀 때 만든 함수들은 다음과 같다.
- rotate(key)함수 - 전달받은 key를 시계 방향으로 90도 돌린 결과를 반환
- move(key, v, h) - 전달받은 key를 수직 방향으로 v, 수평 방향으로 h만큼 이동하는 함수이다. (v와 h는 음수가 될 수 있다)
- getAllKeyCases(key) - 모든 key 케이스를 구해 하나의 리스트로 반환한다.
- checkSuccess(key, lock, v, h) - 현재 key를 수직 방향으로 v, 수평 방향으로 h 위치부터 lock에 겹쳐 보고 홈이 모두 메워졌는지, 충돌은 없는지 확인하는 함수이다.
말로만 설명하면 얘가 뭐 한건지 싶으니 구현 방법을 아래에 설명하겠다.
- rotate(key)함수
회전에 대한 것은 회전 이전과 이후 좌표 변화들을 통해 규칙을 발견했다.
(a, b)의 좌표는 시계 방향으로 90도 회전하면 (b, N - 1 - a)로 이동하므로, key의 복사본을 생성하고 key를 순환하며 위 공식대로 회전한 값을 넣어 반환하였다.
- move(key, v, h)함수
먼저 key의 복사본을 만들어 0으로 초기화한다.
그리고 key를 탐색하며 copy[i+v][j+h]의 위치에 key[i][j]를 복사하여 key를 수직으로 v, 수평으로 h만큼 이동시킨 것처럼 한다.
이후 수직으로 v, 수평으로 h만큼 이동시킨 복사본을 반환한다.
- getAllKeyCases(key)함수
key가 3x3이라 가정하자.
그럼 모든 key의 move 케이스들은 위 그림처럼 수직 방향으로 -2, 수평 방향으로 -2인 케이스부터 수직 방향으로 +2, 수평 방향으로 +2만큼 이동시킨 케이스까지 총 25개이다.
또한 위 move 케이스가 4번 회전한 케이스마다 존재하므로 총 key case는 4x25인 100개이다.
이 100개의 key case를 구해 반환하는 함수이다.
- checkSuccess(key, lock, v, h)함수
위에서 구한 100개의 key 케이스가 존재할 것이다.
key의 크기와 lock의 크기가 같다면 한 번만 비교하면 되지만, 만약 lock의 크기가 더 크다면?
key가 3x3, lock이 5x5일 경우
위처럼 key를 반복해서 lock에 매치 시켜봐야 한다.
여기서 성공 여부를 판단하는 방법은, 속도 면에선 느리지만 확실한 방법을 사용하였다.
lock을 복사한 배열인 copy를 만들고 수직 좌표 (v, h)위치부터 key의 공간만큼 copy와 key를 비교한다.
copy[i][j], key[i-v][j-h]에 모두 1이거나 모두 0이라면 false를 반환하고, 하나만 1이라면 copy[i][j] = 1을 대입한 후 넘어간다.
이 함수 4가지를 이용해 정답을 구한다.
getAllKeyCases함수를 이용해 모든 key 조작 케이스를 구한 뒤, 각 케이스에 대해 0~N-M의 범위에서 checkSuccess 함수로 성공 여부를 찾는다.
class Solution {
fun solution(key: Array<IntArray>, lock: Array<IntArray>): Boolean {
val cases = getAllKeyCases(key)
val M = key.size
val N = lock.size
for(case in cases){
for(i in 0..N-M){
for(j in 0..N-M){
if(checkSuccess(case, lock, i, j)){
return true
}
}
}
}
return false
}
fun checkSuccess(key: Array<IntArray>, lock:Array<IntArray>, v: Int, h: Int): Boolean{
val copy = Array(lock.size){IntArray(lock.size){0}}
for(i in lock.indices)
copy[i] = lock[i].clone()
val ver = if(key.size + v >= lock.size) lock.size else key.size + v
val hor = if(key.size + h >= lock.size) lock.size else key.size + h
for(i in v until ver){
for(j in h until hor){
if(key[i - v][j - h] == 1 && lock[i][j] == 1) return false
if(key[i - v][j - h] == 0 && lock[i][j] == 0) return false
copy[i][j] = 1
}
}
for(i in copy.indices){
for(j in copy.indices){
if(copy[i][j] == 0) return false
}
}
return true
}
fun getAllKeyCases(key: Array<IntArray>): List<Array<IntArray>>{
val M = key.size
val cases = mutableListOf<Array<IntArray>>()
for(i in -(M-1)..M-1){
for(j in -(M-1)..M-1){
val case = move(key, i, j)
var tmp = rotate(case)
for(k in 0..3){
cases.add(tmp)
tmp = rotate(tmp)
}
}
}
return cases
}
fun rotate(key: Array<IntArray>): Array<IntArray>{
val M = key.size
val copy = Array(M){IntArray(M){0}}
for(i in 0 until M){
for(j in 0 until M){
copy[j][M - 1 - i] = key[i][j]
}
}
return copy
}
fun move(key: Array<IntArray>, ver: Int, hor: Int): Array<IntArray>{
val M = key.size
val copy = Array(M){IntArray(M){0}}
for(i in 0 until M){
for(j in 0 until M){
if(i + ver in 0 until M && j + hor in 0 until M){
copy[i + ver][j + hor] = key[i][j]
}
}
}
return copy
}
}