[알고리즘] - 자물쇠와 열쇠 (2020 카카오 코딩테스트)

• 이번 문제는 자물쇠와 열쇠입니다. 문제 명세 및 입출력 예시는 링크를 참고해주세요!

접근 방식

해당 문제는 알고리즘 분류 상으로 구현, 완전탐색 정도로 분류가 가능할 것 같은데요, 문제 설명이 조금 긴 느낌이 있긴 하지만 함께 제공된 그림과 함께 보면 문제에 대한 이해는 어렵지 않게 가능한 것 같습니다.

key와 lock이라는 2차원 배열이 주어지는데요, M과 N이 최대 20이기 때문에, 각 배열이 최대 400개의 수를 포함하게 됩니다. 따라서 O(N^2)의 시간복잡도로 문제를 접근해도 약 160000 정도의 연산 횟수 밖에 안되기 때문에 시간복잡도 보다는 빠짐없이 탐색을 하는데 중점을 두고 접근했습니다.

처음에는 어떤식으로 완전탐색 해야 할지 감이 안 왔는데요, 최근 공부하며 읽고 있는 이코테 책에서 아이디어를 얻었습니다.

기본적으로 아래의 그림과 같이 lock을 고정한 상태에서, key를 움직이며 lock과 key의 원소를 비교했습니다. 이렇게 한 사이클을 비교한 뒤, key를 90도 회전한 뒤 이 과정을 반복했습니다. 그렇게 회전을 반복하면서 원 상태로 돌아올 때까지 탐색을 반복하며 완전탐색을 진행했습니다.

아이디어 자체는 간단한 편이라서 본격적으로 구현을 시작했는데, 구현 과정에서 코드의 복잡도가 높아져 시간을 많이 썼던 것 같습니다..

구현

기본적으로 앞선 그림에서 나타난 것처럼 각 열과 행은 lock 배열의 행의 길이 (== 열의 길이)인 lock_len과 key 배열의 행의 길이 (==열의 길이)인 key_len을 더한 뒤, 1을 감소시킨 만큼 왼쪽과 아래쪽으로 이동하며 비교를 진행하게 됩니다. key 배열과 lock 배열의 길이를 합한 뒤, 겹치는 부분 하나를 제거한다고 생각하면 될 것 같습니다. 이를 iter_num 이라는 변수에 담고, 행과 열을 반복하며 그 안에서 비교를 진행하게 됩니다.

비교 대상이 되어야 할 key와 lock의 인덱스를 설정하는 부분이 다소 복잡했습니다. 우선 비교되어야 할 최대의 횟수는 key_len으로 제한됩니다. 그렇기 때문에 각 행과 열을 key_len 만큼 다시 반복하면서 비교 대상이 될 key와 lock의 인덱스를 설정해줍니다. key와 lock의 비교 원소를 선택하기 위해 lock_row, lock_col, key_row, key_col이라는 변수를 선언했습니다.

위의 그림은 lock이 고정되어 있는 상태에서, key가 비교를 위해 순회하던 중의 임의의 순간을 표현한 그림입니다. 이때, 위의 숫자와 같이 오른쪽 하단부터 왼쪽 상단 순서로 key와 lock의 각 원소들을 비교했습니다. 이를 위해 lock_row를 i-k로 표현했고, key_row는 key_len - k -1로 표현했습니다. lock_col과 key_col도 같은 논리로 반복 변수들을 통해서 표현했습니다.

기본적으로 key_len 만큼 반복하며 이런 식으로 인덱스를 할당하기 때문에, lock과 key가 겹치지 않은 부분들에 대해서도 불필요하게 인덱스를 설정하게 됩니다. 예를 들면 위 그림의 key 배열의 (1,0)과 (2,0) 원소의 경우가 그렇습니다. 만약 비교까지 진행하게 되면 lock 배열에서 out of index 에러가 발생하기 때문에 이를 처리하기 위해 조건문을 추가해줬습니다. lock_row나 lock_col이 0보다 작아지거나 lock_len 보다 크거나 같아질 경우 해당 반복문을 continue 하도록 진행했습니다.

구현 코드는 아래와 같습니다.

import copy

def solution(key, lock):
    key_len = len(key)
    lock_len = len(lock)
    for rotation_num in range(1, 5):

        key = rotate_key(key, rotation_num)

        iter_num = lock_len + key_len - 1
        # 검사할 행의 위치를 카운트
        for i in range(iter_num):

            # 검사할 열의 위치를 카운트
            for j in range(iter_num):

                # lock을 보존하면서 비교하기 위한 comp_lock
                comp_lock = copy.deepcopy(lock)

                # 돌기 간의 충돌을 체크하기 위한 변수 conflict
                conflict = False

                row_cnt = 0
                for k in range(key_len):
                    # i번만 비교하기 위한 장치
                    if row_cnt > i:
                        break
                    row_cnt += 1

                    lock_row = i - k
                    if lock_row < 0:
                        # 비교 불가능
                        continue
                    if lock_row >= lock_len:
                        # 비교 불가능
                        continue
                    key_row = key_len - 1 - k

                    col_cnt = 0
                    for h in range(key_len):
                        # j번만 비교하기 위한 장치
                        if col_cnt > j:
                            break
                        col_cnt += 1

                        lock_col = j - h
                        if lock_col < 0:
                            # 비교 불가능
                            continue
                        if lock_col >= lock_len:
                            # 비교 불가능
                            continue
                        key_col = key_len - 1 - h

                        # key와 lock의 비교
                        if key[key_row][key_col] == 1 and comp_lock[lock_row][lock_col] == 1:
                            conflict = True
                        if key[key_row][key_col] == 1 and comp_lock[lock_row][lock_col] == 0:
                            comp_lock[lock_row][lock_col] = 1

                # 자물쇠가 열렸는지 체크
                result = check_open(comp_lock)

                if result and conflict == False:
                    return True

    return False

def check_open(lock):
    lock_size = len(lock)
    for i in range(lock_size):
        for elm in lock[i]:
            if elm == 0:
                return False

    return True


def rotate_key(key, r_num):
    if r_num == 1:
        return key

    # 시계 방향 90도 회전
    key_num = len(key)

    new_key = copy.deepcopy(key)
    for i in range(key_num):
        for j in range(key_num):
            # 해당 행 순회
            new_key[j][key_num - (i + 1)] = key[i][j]

    return new_key

Lesson

완전탐색 문제가 아직은 낯설어서 아이디어를 떠올리는 것에도 조금 시간이 걸렸지만, 무엇보다도 탐색 과정에서 index를 설정하는 부분이 복잡했던 것 같습니다. 코드를 짜는 과정에서도 스스로 친 코드가 이해가 안되는 부분들이 자꾸만 생겨서 고생을 했던 것 같습니다. 완전탐색 문제를 추가적으로 공부하면서 더 익숙해지고 간결한 코드를 구현할 수 있도록 노력해야 할 것 같습니다.. 화이팅!

문제 바로가기 👉 2020년 카카오 공채 (프로그래머스)