[프로그래머스] 자물쇠와 열쇠 C++

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

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

 

카카오 2020 공채 1차 기출문제이다.

 

M, N 이 최대 20이어서, 완전 탐색으로 풀어보았다.

완전 탐색을 할 시에는, 4 (열쇠 회전) * (2 * (M - 1) + N)^2 (열쇠 이동) 번 반복하게 된다.

열쇠를 90도로 회전시키고, 이동시키며 자물쇠에 들어가는지 검사한다.

 

2차원 배열 board를 사용해 자물쇠와, 열쇠가 모두 들어갈 수 있는 사이즈를 만들어준다. 그리고 해당 board 에 열쇠와 자물쇠를 배치하고, 검사하는 로직을 타게 한다.

검사하는 로직은 다음과 같다.

1. 자물쇠가 0인데, 열쇠가 1이 아닌 경우

2. 자물쇠가 1인데, 열쇠가 0이 아닌 경우

3. 열쇠가 닿지 않는 자물쇠 부분에 0이 있는 경우

-> 1, 2, 3의 경우는 해당 열쇠로 자물쇠를 열지 못한다

 

29번 테스트케이스에서 실패가 떴었는데, 이것저것 테스트케이스를 추가하면서 놓치는 부분이 없는지 보다가.

열쇠를 이동시키는 부분에서 자물쇠의 제일 마지막 행에 걸쳐지는 부분을 검사를 안하고 있었던 것이었다.

board 와 자물쇠 lock 배열을 검사하는 이중for 문에서 마지막으로 검사하는 인덱스를 n - 1 로 고쳤고 통과했다.

이런 경계 부분 잘 살펴봐야 하는 것 같다.

 

전체 코드는 다음과 같다.

#include <string>
#include <vector>
#include <map>

using namespace std;

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = true;
    int m = key.size();
    int n = lock.size();
    
    // 열쇠 90 회전
    for(int i = 0; i <= 4; ++i) {
        vector<vector<int>> nKey;
        nKey.assign(key.size(), vector<int>(key.size(), 0));
        
        for(int j = m - 1; j >= 0; --j) {
            for(int k = 0; k < m; ++k) {
                nKey[k][(m - 1) - j] = key[j][k];
            }
        }
        
        // 열쇠를 이동시키며 검사
        vector<vector<int>> board;
        board.assign(2 * (m - 1) + n, vector<int>(2 * (m - 1) + n, -1));
        // 자물쇠는 m - 1 위치에 고정
        // 열쇠는 0 ~ (n + m - 1)
        
        for(int u = 0; u < n + m - 1; ++u) {
            for(int v = 0; v < n + m - 1; ++v) {
                
                for(int j = 0; j < m; ++j) {
                    for(int k = 0; k < m; ++k) {
                        board[u + j][v + k] = nKey[j][k];
                    }
                }
                
                // board 와 lock 검사
                // board (m - 1) ~ (n + m - 2)
                // lock 0 ~ n - 1
                bool isPossible = true;
                for(int j = 0; j < n; ++j) {
                    for(int k = 0; k < n; ++k) {
                        if (board[j + m - 1][k + m - 1] != -1) {
                            if (lock[j][k] == 0 && board[j + m - 1][k + m - 1] != 1) {
                                isPossible = false;
                                break;
                            }
                            if (lock[j][k] == 1 && board[j + m - 1][k + m - 1] != 0) {
                                isPossible = false;
                                break;
                            }
                        } else if (lock[j][k] == 0) {
                            isPossible = false;
                            break;
                        }
                    }
                    if (!isPossible)
                        break;
                }
                if (isPossible)
                    return true;
                
                // board clear
                board.assign(2 * (m - 1) + n, vector<int>(2 * (m - 1) + n, -1));
            }
        }
        
        for(int j = 0; j < m; ++j) {
            for(int k = 0; k < m; ++k) {
                key[j][k] = nKey[j][k];
            }
        }
    }
    answer = false;
    return answer;
}