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

문제

프로그래머스 2020 KAKAO BLIND RECRUITMENT - 자물쇠와 열쇠 (Level 3)

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

 

---

문제 풀이

접근 방식

이 문제는 2020 카카오 블라인드 공채 1차 코딩테스트 3번 문제로,

주어진 열쇠로 자물쇠를 열 수 있는지를 판단하는 문제였다.

 

열쇠 영역의 일부분이 자물쇠 영역을 벗어나는 것이 가능하다.

그렇기 때문에 자물쇠 영역을 (M - 1) × 2 + N의 크기로 만들고,

(M-1, M-1)에서부터 자물쇠의 값을 복사하여 열쇠를 가능한 모든 방법으로 맞춰볼 수 있도록 하였다.

(M은 열쇠 영역의 한 변의 길이, N은 자물쇠 영역의 한 변의 길이)

M = key.size();
N = lock.size();
int len = (M - 1) * 2 + N;
vector<vector<int>> board(len, vector<int>(len));
for(int i = 0; i < N; i++){
	for(int j = 0; j < N; j++){
		board[i + M - 1][j + M - 1] = lock[i][j];
	}
}

 

자물쇠 영역을 위와 같이 설정해준 후, 열쇠를 (0, 0)에서 (M + N - 1, M + N - 1) 지점까지 이동시키며

자물쇠 영역의 모든 부분을 채울 수 있는지를 확인해주었다.

 

자물쇠의 모든 부분을 채우는 경우가 존재하면 바로 true를 리턴해주었고,

존재하지 않는 경우에는 열쇠를 시계방향으로 90도 회전시킨 후 위의 과정을 반복하여 답을 구해주었다.

열쇠를 회전시키는 방법은 아래와 같다.

vector<vector<int>> temp_key(M,vector<int>(M));
for(int i = 0; i < M; i++){
	for(int j = 0; j < M; j++){
		temp_key[i][j] = key[M - j - 1][i];
	}
}
key = temp_key;

 

---

풀이 코드 - C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int M,N;

bool check(vector<vector<int>> temp){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(temp[i + M - 1][j + M - 1] != 1)
                return false;                
        }
    }
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    // 보드 만들기
    M = key.size();
    N = lock.size();
    int len = (M - 1) * 2 + N;
    vector<vector<int>> board(len, vector<int>(len));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            board[i + M - 1][j + M - 1] = lock[i][j];
        }
    }
    
    // Key 맞춰보기
    for(int dir = 0; dir < 4; dir++){
        for(int a = 0; a <= len - M; a++){
            for(int b = 0; b <= len - M; b++){
                vector<vector<int>> temp = board;
                for(int i = a; i < a + M; i++){
                    for(int j = b; j < b + M; j++){
                        temp[i][j] += key[i-a][j-b];
                    }
                }
                if(check(temp))
                    return true;
            }
        }
        
        // Key 시계방향으로 90도 회전
        vector<vector<int>> temp_key(M,vector<int>(M));
        for(int i = 0; i < M; i++){
            for(int j = 0; j < M; j++){
                temp_key[i][j] = key[M - j - 1][i];
            }
        }
        key = temp_key;
    }
    return false;
}

실행 결과