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

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

프로그래머스

<풀이>

1. 주어진 자물쇠에 90도씩 회전한 4가지 열쇠를 처음부터 끝까지 맞추어 보면서 맞는 가능한 여부를 출력한다.

​

<해법>

1. 자물쇠에 열쇠를 맞추어 보는 방법.

=> 자물쇠를 자물쇠 크기의 9배인 백그라운드 배열의 가운데에 위치시킵니다. 그 후 키 배열을 백그라운드 처음부터 이동시키면서 자물쇠를 탐색합니다.

 

2. 자물쇠를 풀 수 있는 조건.

=> 자물쇠의 홈 갯수를 미리 파악하고, 탐색해 나가면서 열쇠의 돌기와 자물쇠의 홈이 만나는 갯수를 파악합니다. 이렇게 할 경우, 자물쇠의 홈은 전부 채워졌지만 돌기끼리 만나는 경우가 생길 수 있습니다. 이럴 경우 조건을 걸어주어 넘어가도록 진행하였습니다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int KEY[20][20];
int LOCK[20][20];
int tmpKEY[20][20];
int background[60][60];
int M, N;
int hmCnt = 0;
 
//KEY배열 회전 함수
void rotate() {
    memcpy(tmpKEY, KEY, sizeof(tmpKEY));
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            KEY[j][M - 1 - i] = tmpKEY[i][j];
        }
    }
}
 
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
 
    //키 배열의 가로,세로
    M = key.size();
    //자물쇠 배열의 가로,세로
    N = lock.size();
 
    //주어진 자료 배열에 담기
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            KEY[i][j] = key[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            LOCK[i][j] = lock[i][j];
            //자물쇠 홈 개수 저장
            if (LOCK[i][j] == 0) {
                hmCnt++;
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            background[N + i][N + j] = LOCK[i][j];
        }
    }
 
    for (int i = 0; i < 4; i++) {
 
        //KEY 90도씩 회전
        rotate();
 
        //백그라운드 배열 전체 탐색
        for (int i = 0; i <= 2 * N; i++) {
            for (int j = 0; j <= 2 * N; j++) {
 
                //열쇠의 돌기와 자물쇠의 홈이 맞는 개수
                int cnt = 0;
                //열쇠의 돌기와 자물쇠의 돌기끼리 만나는 경우 판단
                bool isAble = true;
 
                for (int k = 0; k < M; k++) {
                    for (int l = 0; l < M; l++) {
 
                        //index
                        int x = i + k;
                        int y = j + l;
 
                        //영역을 벗어난 부분, 영향X
                        if (x < N || y < N || x >= 2 * N || y >= 2 * N ) {
                            continue;
                        }
 
                        //돌기끼리 만나는 경우 or 홈끼리 만나는 경우, 불가능
                        if (background[x][y] == KEY[k][l]) {
                            isAble = false;
                            break;
                        }
 
                        //열쇠의 돌기와 자물쇠의 홈끼리 만나는 경우, 개수++
                        if (background[x][y] == 0 && KEY[k][l] == 1) {
                            cnt++;
                        }
                    }
                }
 
                if (isAble) {
                    if (cnt == hmCnt) {
                        answer = true;
                        return answer;
                    }
                }
            }
        }
    }
    return answer;
}

 

구현과 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.