[2020카카오블라인드]자물쇠와 열쇠

문제설명

구현문제이다. 구현문제는 늘 그렇듯 글을 잘 읽는게 중요하다.

접근

M과 N을 보면 시행횟수가 적다. 회전하는 경우까지 포함하면 대략 M*N*4(roate수)가 된다. 완전탐색을 적용하면 편하다.

초기 완전탐색 접근 방법은 이렇다.

접근1. DFS를 통한 완전탐색

1. 매 단계 rotate할 건지 이동할 건지 선택.(이때 이동은 이동을 1칸씩 이동으로 정의)
2. 해당 케이스가 자물쇠를 열 수 없다면 계속 탐색
3. baseCase는 rotate4번 다 돌았을 때 또는 이동 범위를 벗어났을 때이다.
4. 이를 DFS로 구현한다.

이렇게 하니까 매단계 rotate구현하는게 너무 빡쎘다. 그리고 이렇게 짜면 비효율적이란 감이 들었다. 따라서 rotate 1회전 후 r,c모두 탐색, 2회전후 r,c 모두 탐색으로 접근하려고 했으나, 이는 DFS로 조합을 구현했을 때 버그가 발생하기 매우 쉽고 예민한(?) 코드였다.

5시간 시간재서 2020공채를 풀었기 때문에 풀지 않고 넘어갔고, 다음 날인 오늘 생각해봤더니 모든 케이스 탐색시 for문 써도 충분히 할 것이라 생각이 들었다.

접근2. for문을 통한 완전탐색

1. rotate 1회 2회 3회 4회(제자리) 일때 for문 돌리기
2. 그 rotate for문 안에 toate된 키를 r,c완전탐색

이렇게 접근하니 생각하기 매우 간결해졌다.

rotate1회 2회 3회등은 기존 key에 rotate된 키를 덮어 씌우면서 매 단계 반복이 가능하게 짤 수 있다.

for _ in range(4):
    key = rotateKey(key)
    for r in range(?):
        for c in range(?):

큰 틀은 이와 같이 접근하면 된다! 그럼 이제 구현해야할 세부사항에 대해 생각해보자.

문제속 구현할 세부사항

1. 자물쇠가 열릴 조건을 테스트 해주는 함수를 구현한다.
2. 2차원 행렬인 key를 rotate해주는 함수를 구현한다.
   • rotate 구현하기가 은근 까다롭더라. 연습좀 해야겠다. 삼성기출문제에서도 나왔던 사고인데 또 헤멨다. rotate 구현만 40분이 걸린 것 같다. 고등학생때 배운 회전변환을 이용하여 구현했다.
   • 고등학교때 배운 회전변환은 원점을 기준으로 회전변환하는 것이므로, 키의 중심을 원점으로 옮길 필요가 있다. 그리고 회전변환 공식적용하면 끝.
3. 범위로 인한 키의 탐색범위 생각. lock을 벗어난 범위도 key가 이동할 수 있다.

자료형 결정

함수든 뭐든 그렇듯 그렇게 함수를 정하고나서 어떤 자료형으로 키와 자물쇠를 받아야 좋을지 고민해볼 필요가 있다.

문제를 잘 읽어보면 열쇠가 풀릴 조건은 다음과 같다.

1. 자물쇠의 어떤 돌기(lock[r][c]=1)부분에 대해 열쇠의 돌기(key[r][c]=1)가 있다면 False
   • 즉, 이는 or조건이다. 돌기부분에 하나라도 열쇠의 돌기가 있다면 열쇠는 안풀린다.
2. 자물쇠의 모든 홈(lock[r][c]=0)부분에 열쇠의 돌기가 들어있다면 True
3. 1,2조건을 모두 만족시켜야 결과적으로 True를 반환한다.

결국 lock의 홈과 돌기를 기준으로 key의 돌기가 있는지 없는지 확인하므로 탐색시간이 O(1)인 set자료형으로 받기로 결정했다. 그리고 여기서 보듯 key 홈은 의미없는 데이터다.

범위처리 때문에도 set이 매우 유용하다.

따라서 key돌기,lock돌기,lock홈을 set으로 선언하고 원소에 해당 좌표를 넣는 방식으로 구현하기로 결정.

구현

def rotate(r, c, M):
    pr = (M - 1) / 2
    pc = (M - 1) / 2
    return int(-c + pc + pr), int(r - pr + pc)

def rotatePoints(points,M):
    rotatedPoints = set()
    for r,c in points:
        rotatedR,rotatedC = rotate(r,c,M)
        rotatedPoints.add((rotatedR,rotatedC))
    return rotatedPoints

def check(keyDolgis,lockHomes,lockDolgis):
    for lockDolgi in lockDolgis:
        if lockDolgi in keyDolgis:
            return False

    for lockHome in lockHomes:
        if lockHome not in keyDolgis:
            return False
    return True

def solution(key, lock):
    m = len(key)
    n = len(lock)

    keyDolgis = set() 
    for c in range(m):
        for r in range(m):
            if key[r][c] == 1:
             keyDolgis.add((r,c))

    lockDolgis = set()
    lockHomes = set()
    for c in range(n):
        for r in range(n):
            if lock[r][c] == 1:
                lockDolgis.add((r,c))
            else:
                lockHomes.add((r,c))

    answer = False
    for _ in range(4):
        keyDolgis = rotatePoints(keyDolgis,m)
        for dr in range(-m+1,m+n-1):
            for dc in range(-m+1,m+n-1):
                movedKeyDolgis = set()
                for kr,kc in keyDolgis:
                    movedKeyDolgis.add((kr+dr,kc+dc))
                isOpen = check(movedKeyDolgis,lockHomes,lockDolgis)
                if isOpen is True:
                    answer = True
                    return answer

    return answer