[프로그래머스 60059] - 카카오 자물쇠와 열쇠

문제 출처

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

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

 

 

문제 풀이

전체탐색과 2차원 배열을 다룰 수 있는지 묻는 문제 입니다.

자물쇠에 키를 대조할때 겹치면 안되나 키가 자물쇠의 범위를 벗어나도 된다는 것이 핵심입니다. 
즉 키의 (0,0) 부분이 map의 (0,0) ~ (n+m-1, n+m-1)까지 이동하며 탐색하면 됩니다.

아래 그림은 자물쇠와 키의 예시입니다.

map을 확장한뒤 map[n+2m-2][n+2m-2]의 정 중앙에 자물쇠를 두어 겹치게 한다면 전체탐색이 가능합니다.

즉 탐색을 좌측상단 열쇠위치에서 시작하고 마지막 탐색은 우측하단 열쇠 위치까지 진행하여 열쇠와 자물쇠가 적합한지 판단하는 문제입니다.

탐색한 뒤 키와 자물쇠가 중복되지 않은 것을 판별하기 위해 map에서 자물쇠 위치를 탐색할때 배열에 있는 값이 1이 아니면 false를 return합니다.

 

 

소스 코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EC%9E%90%EB%AC%BC%EC%87%A0%EC%99%80%20%EC%97%B4%EC%87%A0.cpp

sw93/algorithm

 

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

void rotateKey(vector<vector<int>> &key) {
    int keySize = key.size();
    vector<vector<int>> temp = key;
    for (int y=0; y<keySize; y++) {
        for (int x=0; x<keySize; x++) {
            key[y][x] = temp[keySize-x-1][y];
        }
    }
}

bool isUnlock(int sy, int sx, vector<vector<int>> key, vector<vector<int>> map) {
    int keySize = key.size();
    int mapSize = map.size();
    
    for (int y=sy; y<sy+keySize; y++) {
        for (int x=sx; x<sx+keySize; x++) {
            map[y][x] += key[y-sy][x-sx];
        }
    }

    for (int y=keySize-1; y<mapSize-keySize+1; y++) {
        for (int x=keySize-1; x<mapSize-keySize+1; x++) {
            if (map[y][x] == 1) continue;
            return false;
        }
    }
    
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int keySize = key.size();  
    int lockSize = lock.size(); 
    int mapSize = lockSize + (keySize-1)*2; 

    // 작업할 map생성
    vector<vector<int>> map(mapSize, vector<int>(mapSize, 0));
    for (int y=0; y<lockSize; y++) {
        for (int x=0; x<lockSize; x++) {
            map[y+keySize-1][x+keySize-1] = lock[y][x];
        }
    }
    
    // 90도씩 4번 회전
    for (int i=0; i<4; i++) {
        // key를 전체 map에 대해 탐색
        for (int y=0; y<mapSize-keySize+1; y++) {
            for (int x=0; x<mapSize-keySize+1; x++) {
                if (isUnlock(y, x, key, map)) {
                    return true;
                }
            }
        }
        rotateKey(key);
    }
    
    return false;
}