프로그래머스 60059(자물쇠와 열쇠)

📜 문제

문제링크
2차원 배열 구현 + 완전탐색 유형의 문제였다. (카카오기출)

---

📖 풀이

처음 문제를 봤을때, 어떻게 key 의 모든 case 들을 lock 에 넣어볼 수 있을지 감이 잡히지 않아 풀이를 떠올리는데 시간이 오래 걸렸다.

위의 그림과 같이 [n + 2 * m - 2][n + 2 * m - 2] 크기의 배열을 선언하고 (0,0) ~ (m + n - 2, m + n - 2) 까지 key 배열을 돌면서 열쇠로 자물쇠를 열 수 있는 경우가 있는지를 확인하면 문제에서 제시하는 key 를 움직이는 경우에 대해서 모두 확인할 수 있다.

다음은, key 를 회전하는 경우이다. key 를 시계방향으로 90도 회전하는 경우, 하나의 key 에 대해서 총 4가지 case 가 존재하고 4가지 모든 case 에 대해서 위의 방법을 이용에 key 를 움직여 보면서 열쇠로 자물쇠가 여는 경우가 있는지 확인해보면 모든 case 를 확인할 수 있다.

1. 공간복잡도

   1) [n + 2 * m - 2][n + 2 * m - 2] 크기의 배열 x 2

최악의 경우에도 배열의 크기는 [58][58] 이므로 역시 메모리 초과를 걱정할 필요는 없다.

2. 시간복잡도

   1) board 에 key 값들을 더하며 모든 case를 확인하는 과정 O(m^4 * n^2)

위의 경우를 최악의 경우 key를 4번 회전 시키기 때문에 4 * 6.4 * 10^7 정도가 된다. 나머지 과정들이 모두 더해지더라도 약 1초 이내에 문제 해결이 가능하다.

---

🖥 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int board[60][60], board_temp[60][60];
int m,n;

//시계방향 90도 회전 구현
void rotate_arr(vector<vector<int>>& key) {
    int temp[60][60];
    for(int y = 0; y < m; y++)
        for(int x = 0; x < m; x++)
            temp[x][m - 1 - y] = key[y][x];
    
    for(int y = 0; y < m; y++)
        for(int x = 0; x < m; x++)
            key[y][x] = temp[y][x];
}

bool isPossible() {
    for(int y = m - 1; y < m + n - 1; y++)
        for(int x = m - 1; x < m + n - 1; x++)
            if(board_temp[y][x] != 1)
                return false;
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    
    m = key.size();
    n = lock.size();
    
    for(int y = m - 1; y < m + n - 1; y++)
        for(int x = m - 1; x < m + n - 1; x++)board[y][x] = lock[y - m + 1][x - m + 1];
        
    bool answer = false;
    for(int dir = 0; dir < 4; dir ++) {    
        rotate_arr(key);
        for(int y = 0; y < m + n - 1; y++){
            for(int x = 0; x < m + n - 1; x++){
                
                //board_temp 초기화!
                for(int y = 0; y < n + 2 * m - 2; y++)
                    for(int x = 0; x < n + 2 * m - 2; x++)
                        board_temp[y][x] = board[y][x];
                
                //board_temp에 key 값들을 더해봄
                for(int yy = y; yy < y + m; yy++){
                    for(int xx = x; xx < x + m; xx++){
                        board_temp[yy][xx] += key[yy - y][xx - x];        
                    }
                }
                /*
                cout << "-----------------------\n";
                for(int y = 0; y < n + 2 * m - 2; y++){
                    for(int x = 0; x < n + 2 * m - 2; x++){
                        cout << board_temp[y][x] << ' ';
                    }
                    cout << '\n';
                }
                */
                if(isPossible())return true;
            }
        }
    }
    return answer;
}

---

🔨 피드백

풀이를 떠올리고 구현하는데도 약간의(?) 시행착오가 있었다.
프로그래머스에서 변수의 자료형이 정해져 있는데 평소 왠만한 변수들을 전역변수로 선언해 다른 함수에서 사용하던 습관 때문에 힘들었다.

key 값들을 회전하기 함수를 구현해 실제 key 값들을 바로 회전 하기 위해서 call -by- ref 방식을 이용했다.

void rotate_arr(vector<vector<int>>& key) {
    int temp[60][60];
    for(int y = 0; y < m; y++)
        for(int x = 0; x < m; x++)
            temp[x][m - 1 - y] = key[y][x];
    
    for(int y = 0; y < m; y++)
        for(int x = 0; x < m; x++)
            key[y][x] = temp[y][x];
}

실제 함수를 보면 temp 배열에 회전값을 임시 저장하고 이를 다시 key 값에 저장해주는 방식이다. 처음 구현할때, 회전을 생각해주는게 생각보다 까다로웠는데 문제에서 예시로 주어진 3*3 행렬을 그려서 검증했다. (이해가 안될때는 간단한 예제를 직접 손으로 풀어보자.)

❗️이런 2차원 배열 문제는 직접 손으로 풀어보는게 확실히 코드 구현하기가 더 쉬워지는 것 같다!