이 포스팅에서는 2020 카카오 블라인드 채용 1차 문제인 ‘자물쇠와 열쇠’ 문제를 해설합니다. 본 풀이에 대한 테스트는 https://programmers.co.kr/learn/courses/30/lessons/60059에서 수행하였으며 공식 풀이와 일치하지 않을 수 있습니다.
공식 풀이는 링크를 참조하시기 바랍니다.
출처 : 2020 KAKAO 블라인드 채용 온라인 1차
링크 : https://programmers.co.kr/learn/courses/30/lessons/60059
카테고리 : Backtracking
난이도 : 보통
자물쇠와 열쇠가 주어진다. 자물쇠의 모든 홈을 열쇠의 돌기로 채우면 자물쇠가 풀린다. 열쇠는 회전시킬 수도 있고 열쇠의 일부만 자물쇠에 집어넣을 수 있다. 단 열쇠의 돌기와 돌기가 닿아서는 안된다.
단순히 직관적인 답은 열쇠를 90도씩 회전시켜보면서, 끼워맞춰 볼 수 있는 모든 경우를 다 시도해보고 그 중 가능한 것이 있는지 살펴보는 것이다.
90도 회전 연산은 다음과 같다. 가로 세로 길이가 N인 격자에서 왼쪽 최상단 좌표를 (0,0) 이라고 할 때 점 (x, y)는 (N – y – 1, x)가 된다. 이 연산은 (0, 0)과 (N – 1, N – 1)을 지나는 직선에 대해 (x, y)를 대칭 연산을 하고 x = (N – 2) / 2 직선에 대해 대칭 연산을 수행한 것과 같다.
열쇠의 크기를 M x M, 자물쇠를 N x N 이라고 하자. 여기서 (0, 0)의 기준점이 가리키는 지점이 열쇠와 자물쇠에서 다르다. 열쇠에 대해서 (0, 0)은 열쇠의 오른쪽 맨 하단을 가리킨다. 자물쇠에 대해서는 왼쪽 최상단을 가리킨다. 원래 자물쇠와 같은 기준점을 가지고 있었던 열쇠를 90도 방향으로 두 번 회전했다고 생각해보자. 그러면 지금과 같이 변환이 된다.
불행하게도 위의 아이디어는 필자가 문제 풀이를 할 당시에는 생각하지 않았기 때문에, 좀 더 복잡한 방식을 가지고 진행한다. 즉, 열쇠와 자물쇠 모두 왼쪽 최상단 지점을 (0, 0)으로 설정한 상태에서 매칭을 진행한다. 자물쇠의 기준에서 볼 때 열쇠의 (0, 0)은 (-M + 1, -M + 1)과 같다.
자물쇠는 가만히 두고 열쇠를 가능한 가장 위쪽 지점에서부터 왼쪽에서 오른쪽 방향으로 이동시키면서 매칭을 진행할 것이다. 예를 들어 열쇠가 3 x 3이고 자물쇠가 5 x 5라면 맨 처음에는 열쇠의 (2, 2) 지점과 자물쇠의 (0, 0) 지점으로 매칭을 해보고 그 다음에는 열쇠를 한 칸 오른쪽으로 이동시켜 열쇠의 (2, 2), (1, 2) 지점과 자물쇠의 (0, 0), (1, 0) 지점을 매칭시켜보는 것이다. 이렇게 가로로 이동하다가 마지막으로 열쇠의 (0, 2) 지점과 자물쇠의 (4, 0) 지점을 매칭해보고 다시 처음으로 돌아가 열쇠를 아래로 한 칸 이동시키고 같은 과정을 진행한다.
for문은 열쇠와 자물쇠가 최소한 하나 이상의 영역을 공유하는 범위에 대해서만 수행된다.
열쇠와 자물쇠가 겹치는 영역에 대해 가장 왼쪽 상단의 좌표를 얻어보자. 이 좌표는 자물쇠를 기준으로 한 좌표이다. 현재 열쇠에서 M – 1열에 해당하는 부분이 자물쇠의 i열에 존재한다고 생각해보자. 그렇다면 열쇠의 0번 열은 자물쇠에 대해 i – M – 1 열에 존재하는 것이다. 이 열이 0보다 작다는 것은 자물쇠 밖에 해당 열이 존재한다는 것이다. 즉, 겹치는 영역의 가장 왼쪽 좌표는 0이나 i – M – 1 중에서 큰 값이다.
같은 원리로 겹치는 영역의 가장 상단의 좌표는 0이나 j – M – 1 중에서 큰 값이다. 여기서 j는 열쇠에서 M – 1행에 해당하는 부분이 자물쇠의 j행에 존재한다고 가정할 때의 값이다.
겹치는 영역의 가장 우측의 좌표는 열쇠의 M – 1열이 위치한 i열 또는 자물쇠의 끝인 N – 1열이다. 가장 하단의 좌표도 마찬가지다.
열쇠의 M – 1열에 해당하는 부분이 자물쇠의 i열에 존재한다고 생각해보자. 그렇다면 자물쇠의 0번열은 열쇠의 M – 1 – i열에 해당한다. 위에서 구한 자물쇠 영역의 x좌표를 lock_x라고 하고 지금 구할 열쇠 영역을 key_x라고 하면 key_x = M – 1 – i + lock_x가 된다.
같은 원리로 key_y = M – 1 – i + lock_y가 된다.
자물쇠 영역 구하기에서 가장 왼쪽 오른쪽의 좌표와 가장 상단 하단의 좌표를 구했으므로 그 값을 통해 구할 수 있다.
이제 각자의 좌표계 대해 시작점과 사이즈를 알았기 때문에 직접 매칭을 시켜보면 된다. 미리 자물쇠에 있는 홈의 개수를 세어놓고, 열쇠의 돌기가 자물쇠의 홈을 채우는 경우가 그 수와 일치하는지 비교하면 된다.
def isMatch(key, lock, lock_x, lock_y, key_x, key_y, size_x, size_y, goal): cnt = 0 for i in range(size_x): for j in range(size_y): if lock[lock_x + i][lock_y + j] ^ key[key_x + i][key_y + j] == 0: return False if key[key_x + i][key_y + j] == 1: cnt += 1 return cnt == goal def backtracking(key, lock, goal): M, N = len(key), len(lock) for i in range(0, N + M – 1): for j in range(0, N + M – 1): lock_x = max(i – M + 1, 0) lock_y = max(j – M + 1, 0) key_x = lock_x – (i – M + 1) key_y = lock_y – (j – M + 1) size_x = min(i, N – 1) – lock_x + 1 size_y = min(j, N – 1) – lock_y + 1 if isMatch(key, lock, lock_x, lock_y, key_x, key_y, size_x, size_y, goal): return True return False def rotate(key): M = len(key) new_key = [[0] * M for i in range(M)] for i in range(M): for j in range(M): new_key[M – 1 – j][i] = key[i][j] return new_key def solution(key, lock): Sum = sum(sum(line) for line in lock) if Sum == len(lock) ** 2: return True goal = len(lock) ** 2 – Sum for i in range(4): if backtracking(key, lock, goal): return True key = rotate(key) return False | cs |
Competition 카카오 블라인드 채용 자물쇠와 열쇠
Planning A well-structured plan has the following characteristics: First, the ultimate vision you aim to…
English The most common problem for English learners like myself is that we often use…
This website uses cookies.