Question

python 풀이 방법 공유합니다(코드 O, 힌트 O)

쉽지 않은 난이도에 다른 분들이 여러 풀이를 올려주셨지만 꽤 오랜 시간이 걸려 풀었는데요,
문제 풀이 힌트를 보고자 하시는 분들은 이 글을 한번 읽어주세요.
혹시 코드는 보고 싶지 않으시다면 아래에 있을 코드에 주의해주세요.

자물쇠와 열쇠의 크기가 다를 수 있고, 자물쇠의 크기보다 더 큰 배열을 새롭게 선언해서 푸는 방법을 생각할 때, 배열의 크기를 가장 효과적으로 잡는 방법은 딥러닝 cnn의 filter가 이미지를 훑고 가는 방식과 비슷하게 생각하면 가장 편합니다.
예를 들어 0으로 채워진 2x2(M=2) 크기의 열쇠와 1로 채워진 3x3(N=3) 크기의 자물쇠가 있을 때 떠올릴 배열은
0 0 0 0 0
0 * 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
위 배열과 같이 5x5(N+(M*2)-2) 크기의 배열입니다. 열쇠의 처음 위치는 가장 왼쪽 위 4칸부터 시작해 자물쇠와 겹치는 *부터 확인하며 차례대로 좌->우 확인 후 한 칸 아래로 내려와 다시 좌->우로 확인하는 방식을 반복하면 됩니다.
이후 처음 4칸에서 회전한 키가 다시 좌우, 상하로 지나가며 자물쇠와 맞는지 훑고 지나가는 방식입니다.

이때 위처럼 머리로 생각하되 실제 배열을 선언하지 않고 좌표만 가지고 와서도 풀 수 있는데요, 자물쇠의 위치는 (M-1, M-1) ~ (N+M-2, N+M-2)로 생각하고, (회전한) 열쇠의 좌표는 (0, 0) ~ (M, M)으로 위 배열로 생각했을 때 4칸 중 1인 좌표만 가져와 차례대로 이동하며 확인할 수 있습니다.

주의해야 할 점은 열쇠의 좌표가 자물쇠의 0인 홈을 다 채워도 돌기와 만나면 안 된다는 점인데요, 위 배열을 떠올리실 때 회전된 열쇠의 1인 좌표 중 자물쇠의 홈과 일치하지 않으면서 (M-1) <= x, y좌표 <= (N+M-2) 범위 내에 존재한다면 돌기와 만나는 것으로 해당 case는 넘어가야 합니다.

아래 제가 작성한 코드는 이 글을 적으면서 좀 더 가시성 있게 함수와 반복문을 나눈 것으로, 코드적으로 더 깔끔하고 효율적인 코드는 얼마든지 있을 수 있습니다.

저처럼 많이 어려워하시는 분들도 위에 적힌 방식으로 차근차근 진행하신다면 충분히 푸실 수 있을 거라 생각합니다.
긴 글 읽어주셔서 감사하고 의견과 댓글 편하게 남겨주시면 확인하고 답글 달겠습니다 :)

작성중인 코드―solution.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import copy
def solution(key, lock):
    answer = False
    M = len(key)
    N = len(lock)
    keys = []
    locks = []

    for i in range(M):
        for j in range(M):
            if key[i][j] == 1: keys.append([i, j])
    keys_len = len(keys)

    for i in range(N):
        for j in range(N):
            if lock[i][j] == 0: 
                locks.append([i+M-1, j+M-1])

    def rotate_90(keys):
        key_90 = []
        for k in keys:
            key_90.append([k[1], M-k[0]-1])
        return key_90

    def rotate_180(keys):
        key_180 = []
        for k in keys:
            key_180.append([M-k[0]-1, M-k[1]-1])
        return key_180

    def rotate_270(keys):
        key_270 = []
        for k in keys:
            key_270.append([M-k[1]-1, k[0]])
        return key_270

    def check_key(moved_key):
        if len(moved_key) < len(locks): return False # 애초에 홈을 전부 채우지 못 한다면 False
        checking = 0
        for k in moved_key:
            if k in locks: checking += 1
            elif ((M-1) <= k[0] <= (N+M-2)) and ((M-1) <= k[1] <= (N+M-2)): return False
        if checking == len(locks): return True
        return False

    def move_key(rotated_keys):
        for i in range(N+M-1):
            moved_key = copy.deepcopy(rotated_keys)
            for k in range(keys_len):
                moved_key[k][0] = rotated_keys[k][0] + i
            for j in range(N+M-1):
                for k in range(keys_len):
                    moved_key[k][1] = rotated_keys[k][1] + j
                if check_key(moved_key): return True
        return False

    if move_key(keys): return True

    key_90 = rotate_90(keys)
    if move_key(key_90): return True

    key_180 = rotate_180(keys)
    if move_key(key_180): return True

    key_270 = rotate_270(keys)
    if move_key(key_270): return True

    return answer

HS

2024.2.28 20:36

python 풀이 방법 공유합니다(코드 O, 힌트 O)

작성중인 코드―solution.py

0 개의 답변

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다.