[알고리즘] 카카오 공채 - 자물쇠와 열쇠 Python

안녕하세요

오랜만에 알고리즘 풀이를 포스팅해보려 합니다 :)

오늘 포스팅할 문제는 카카오 blind recruitment에 나왔던 '자물쇠와 열쇠' 입니다. 

programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

 

[문제 설명]

 

[제한사항 & 입출력 예]

 

이 문제는 2차원 배열을 잘 다룰 수 있는지 확인하는 문제로, 2차원 배열의 회전과 이동방법을 구현해서 완전탐색을 수행하면 풀리는 문제입니다. 

 

[접근 방식]

1. key가 회전 가능하기 때문에, key를 회전시키기 위한 rotate함수 만들기 

2. key와 lock의 크기를 포함하는 2차원 배열 생성 & 가운데에 lock 배치 (코드에서 make_grid함수)

3. key를 이동시키기 위한 translate 함수 만들기 

4. key와 lock이 일치하는지 확인하는 is_unlock함수 만들기 (key와 lock이 일치하면 무조건 1이기 때문에 lock의 행과 열을 순회하면서 1이 아닌 원소를 만나면 false리턴 모두 1이면 true 리턴)

5. translate함수를 통해 1칸씩 옆으로 움직이며 key와 lock이 일치하는지 is_unlock함수를 통해 확인, 열이 끝나면 한칸 아래로 이동

6. 모든 행과 열을 움직였음에도 일치하는 key가 없다면 90도 회전시킨 키로 1~5 과정 반복 

 

[파이썬 코드]

import copy

def solution(key, lock):
    M = len(key)
    N = len(lock)
    
    def rotate(key):
        ret = [[0] * M for _ in range(M)]

        for r in range(M):
            for c in range(M):
                ret[c][M-1-r] = key[r][c]
        return ret
    
    def make_grid(lock):
        grid = [[0] * (M + (N-1) * 2) for _ in range(N + (M-1) * 2)]
        
        for r in range(N):
            for c in range(N):
                grid[M-1+r][M-1+c] = lock[r][c]
        return grid
      
    def translate(grid, key, row_step, col_step):
        for r in range(M):
            for c in range(M):
                grid[row_step+r][col_step+c] += key[r][c]
        return grid
    
    def is_unlocked(grid):
        for r in range(M-1,M+N-1):
            for c in range(M-1,M+N-1):
                if grid[r][c] != 1:
                    return False
        return True 
    
    grid = make_grid(lock)
    key1 = rotate(key)
    key2 = rotate(key1)
    key3 = rotate(key2)
    
    for key in [key,key1,key2,key3]:
        for row_step in range(N+M-1):
            for col_step in range(N+M-1):
                g = translate(copy.deepcopy(grid), key, row_step, col_step)
                
                if is_unlocked(g):
                    return True
    
    return False