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

 

 

 

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

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

 

완전 꼬여서 못풀다가

 

힌트 보고 나서야 풀었다.

 

내가 풀던 방식은 dfs로 경로를 찾아서 5가지의 이동중(상, 하, 좌, 우, 회전) 맞물리는 경우를 찾으려고 했던 거였다.

 

근데 잘 안됨.

 

그래서 전체 board(key+lock 실행할 큰 판)를 두고 맞물리는지 브루트포스로 풀면 된다는 힌트를 보고 품.

 

맨 처음에 board에 lock 자리에 lock과 똑같이 0, 1을 넣어놓는다.

 

그리고 key를 board의 맨 왼쪽부터 맨 끝까지 이동하면서 board에 key 값들을 더해본다.

 

이때 board에서 lock자리의 값들 중 0(key가 안들어감)이나 2(돌기가 겹침)가 있으면 key와 안맞다는 거고

모두 다 1이면 맞는다는 거다.

 

그렇다 다 이동시켰는데 안맞으면 key를 총 4번 회전시켜보고 그래도 아니면 false가 답이다.

 

 

 

 

 

Code

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

using namespace std;

// key를 시계방향 회전
vector<vector<int>> rotate_key(vector<vector<int>> key) {
    vector<vector<int>> tmp(key.size(), vector<int>(key.size(), 0));
    int m = key.size();
    
    for(int i=0; i<m; i++) {
        for(int j=0; j<m; j++) {
            if(key[i][j] == 1) {
                tmp[j][m-1-i] = 1;
            }
        }
    }
    return tmp;
}

// 다 잘 물렸는지 확인
bool check_board(vector<vector<int>> board, int m, int n) {
    for(int i=m-1; i<n+m-1; i++) {
        for(int j=m-1; j<n+m-1; j++) {
            if(board[i][j] == 2 || board[i][j] == 0) return false;
        }
    }
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    int n = lock.size(), m = key.size();
    vector<vector<int>> board(n+2*m-2, vector<int>(n+2*m-2, 0)), tmp(n+2*m-2, vector<int>(n+2*m-2, 0));
    
    // lock을 board 중앙에 더해놓기
    for(int i=m-1; i<m+n-1; i++) {
        for(int j=m-1; j<m+n-1; j++) {
            board[i][j] = lock[i-m+1][j-m+1];
        }
    }    
    
    int ti = 0, tj = 0;
    int cnt = 0;
    while(1) {
        if(check_board(tmp, m, n)) {
            answer = true;
            break;
        }
            
        tmp = board;
        
        // 전체적으로 이동하면서 key와 맞물려보기
        for(int i=0+ti; i<m+ti; i++) {
            for(int j=0+tj; j<m+tj; j++) {
                tmp[i][j] += key[i-ti][j-tj];
            }
        }
        
        if(tj == m+n-2) {
            tj = 0;
            if(ti == m+n-2) {
                ti = 0;
                tj = 0;
                
                // 한번 전체 이동 다 해봤으면 key 회전 (총 4번)
                if(cnt != 4) {
                    key = rotate_key(key);
                    cnt++;
                    continue;
                }
                break;
            }
            else ti++;
        }
        else tj++;
    }
    
    return answer;
}