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

코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

코드 원본:

[c++][프로그래머스] 자물쇠와 열쇠 (tistory.com)

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

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

int k, l, b;//key.size, lock.size, board.size 전역변수 설정

void rotate_key(vector<vector<int>> &key) {
    vector<vector<int>> tmp(k, vector<int>(k, 0));
    for(int i=0; i<k; ++i)
        for(int j=0; j<k; ++j)
            tmp[i][j] = key[k-(j+1)][i];
    key = tmp;
}

bool check(vector<vector<int>> &board, vector<vector<int>> &key, int y, int x) {
    bool ret = true;
    for(int i=0; i<k; ++i)
        for(int j=0; j<k; ++j)
            board[y + i][x + j] += key[i][j];
    
    for(int i=0; i<l; ++i)// 가운데 lock 영역이 모두 1이면 true, 아니면 false
        for(int j=0; j<l; ++j)
            if(board[k-1 + i][k-1 + j] != 1)
            {
                ret = false;
                break;
            }
    
    for(int i=0; i<k; ++i)
        for(int j=0; j<k; ++j)
            board[i+y][j+x] -= key[i][j];
    
    return ret;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    k = key.size();
    l = lock.size();
    b = 2*(k-1) + l;//board.size
    
    vector<vector<int>> board(b, vector<int>(b, 0));
    
    for(int i=0; i<l; i++)    // 가운데에 lock 영역 두기
        for(int j=0; j<l; j++)
            board[k-1 + i][k-1 + j] = lock[i][j];
    
    for(int r=0; r<4; r++)
    {
        for(int i=0; i<=b-k; ++i)
            for(int j=0; j<=b-k; ++j)
                if(check(board, key, i, j)) return true;
        rotate_key(key);   
    }
    
    return false;
}

문제를 어떻게 푸는지 그려지긴 했지만.. 도무지 도무지 4중 ~5중포문을 돌려야 한다는것이 믿기지 않아서 참고를 많이 한 문제임..

우선 문제의 키포인트 첫번째

1)키를 회전할 수 있다.

규칙을 찾았는데 이는 4방면의 경우에 같은 규칙으로 통일될 수 있었다.

    for(int i=0; i<k; ++i)
        for(int j=0; j<k; ++j)
            tmp[i][j] = key[k-(j+1)][i];

이런식으로 하고 key = temp;로 하면 키값이 변형되어 90도 회전한 상태로 바꿀 수 있다.

우리가 함수의 매개변수를 참조자로 받았기 때문에 가능하다.

 

(우리가 정의한 함수들에서 필요한 전역변수들은 선언만 전역으로 해주고 main에서 초기화해줄 수 있음.

좋은 아이디어이니 참고하자.)

 

키포인트 두번째

2)키는 lock과 아주 일부만 겹쳐도 된다.

그림으로 치면 이러한 경우가 가능한 것임.

내가 참조한 블로그의 경우, board라는, key가 하나라도 겹칠 수 있는 새로운 크기의 2차원벡터를 선언, 그 값을 0으로 초기화해주었음

vector<vector<int>> board(b, vector<int>(b, 0));

2차원 벡터의 초기화는 이를 참고하자  ( board(초기화하고싶은 숫자, 초기화 형태); )

 

맨 첨에 board의 가운데에다가 (k-1, k-1)부터...lock.size만큼 lock을 할당해주는 초기화를 진행한다.

 

이후에 check를 진행하는데, 이는 

위 그림에서 1에 해당하는 순간부터 2가 될 때까지 slide하면서 그때마다 체크해주어야 하고

처음 키의 방향로 모든 체크가 끝났다면 90도 회전한 키로 다시 슬라이드하며 체크를 해주어야 함.

 

check에서는 board기준 (0,0)부터 해서 key의 값을 더해주고

board에서 lock에 해당하는 위치의 모든 값이 1이 되지 않은 경우는 false를 return 해줌

 

조건을 달성하지 못했을 시엔 더해줬던 key를 그대로 다시 빼서 다시 진행이 가능하게 한다.

 

이렇게 해서 한번이라도 check의 값이 true라면 결과도 true, 아니라면 false가 된다.