프로그래머스 - 자물쇠와 열쇠 (C++)

Pixabay로부터 입수된 Štefan님의 이미지 입니다.

---

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

프로그래머스

 

 이 문제는 정사각형 모양의 키와 자물쇠가 주어졌을 때, 키를 회전해서 자물쇠의 모든 홈을 채울 수 있는지를 검사하는 문제이다. 이 문제를 처음 접했을 때는 알고리즘에 대해 거의 아무것도 모르던 때라 다른 풀이를 참고해서 풀었었다. (하단의 링크 참조) 그 후, 시간이 지나서 혼자 풀어보려고 해도 계속 참고했었던 풀이만 생각이 나서 이 문제를 기록해도 될까 망설였지만 그냥 기록하기로 했다. 

 

검은선: 자물쇠 / 초록선: 키 / 빨간선: 자물쇠 확장한 것

 각설하고, 본인은 이 문제를 구현 문제라 생각하였다. 그래서 자물쇠랑 키를 일일이 맞춰보면 되는 문제라 생각했다. 그런데 난감한 점이 하나 있다. 그것은 키의 모든 부분이 자물쇠랑 매칭되지 않아도 된다는 것이다. 그렇기에 이 부분을 어떻게 구현할지 굉장히 고민했었다. 그런데 이에 대한 해법은 아주 간단했었다. 자물쇠를 위 그림처럼 확장한 후, 키를 확장한 자물쇠의 왼쪽 위부터 오른쪽 아래까지 검사를 진행하면 된다. 그리고 이 때의 자물쇠의 행, 열의 길이는 각각 자물쇠의 행 + 키의 행 x 2 - 2, 자물쇠의 열 + 키의 열 x 2 - 2 이다. 우선 행을 기준으로, 자물쇠는 가운데에 위치시키고 키를 움직이면서 검사할 것이기에 행의 길이는 자물쇠의 행 + 키의 행 + 키의 행 이다. 그리고 위의 자물쇠-키 그림처럼, 검사를 하기 위해서는 적어도 행에서 끝부분 한 칸 씩 켭쳐야 한다. 이 한 칸은 행 기준으로 두 개가 존재한다. 그렇기에 행의 길이는 자물쇠의 행 + 키의 행 + 키의 행 - 2이며 열 역시 마찬가지이다. 그렇기에 이를 감안하여 자물쇠를 확장시킨 후, 키를 왼쪽 끝부터 오른쪽 아래까지 일일이 검사한다. 그리고 키가 모든 홈을 채우는 경우가 없다면, 키를 회전시킨 후 이를 다시 진행한다. 이를 감안한 풀이 과정은 다음과 같다.

1. 자물쇠를 자물쇠 길이와 키 길이를 고려하여 확장시킨다.
2. 확장된 자물쇠에서 키-자물쇠 검사를 시작할 지점을 고른 후, 모든 홈을 채울 수 있는지 검사한다.
3. 만약 모든 홈을 채울 수 있다면 true를 반환하고 그렇지 않다면 키를 회전한 후 다시 검사한다.
4. 키를 4번(정사각형은 4번 회전하면 원래 모습이 됨) 회전을 시켰음에도 모든 홈을 채울 수 없다면 false를 반환한다.

 

#include <string>
#include <vector>

using namespace std;

int blankNum = 0;               // 자물쇠의 홈의 개수
int keyR, keyC;                 // 키의 행 길이, 열 길이
int lockR, lockC;               // 자물쇠의 행 길이, 열 길이
vector<vector<int>> wideLock;   // 자물쇠의 확장판

// 키를 회준시키는 함수
vector<vector<int>> Rotate(vector<vector<int>> key)
{
    vector<vector<int>> rotated = key;
    
    for (int r = 0, kC = 0; r < rotated.size(); ++r, ++kC)
    {
        for (int c = 0, kR = key.size() - 1; c < rotated[r].size(); ++c, --kR)
            rotated[r][c] = key[kR][kC];
    }
    
    return rotated; // 회전된 키를 반환한다.
}

// 현재 시작 좌표에서 키가 모든 홈을 매울 수 있는지 검사하는 함수
bool Check(int startR, int startC, vector<vector<int>> key)
{
    int leftBlankNum = blankNum;    // 남은 홈의 개수
    
    for (int r = 0, wideR = startR; r < keyR; ++r, ++wideR)
    {
        for (int c = 0, wideC = startC; c < keyC; ++c, ++wideC)
        {   
            // 문제의 조건
            // 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다.
            if (key[r][c] == 1 && wideLock[wideR][wideC] == 1)
                return false;
            
            // 키의 돌기 + 자물쇠의 홈
            if (key[r][c] == 1 && wideLock[wideR][wideC] == 0)
                --leftBlankNum;
        }
    }
    
    return leftBlankNum == 0;   // 남은 홈의 개수가 0일 경우 true, 아니면 false
}

// 자물쇠 확장판에서 시작 좌표를 지정하여
// 모든 홈을 매울 수 있는지 검사하는 함수
bool CanFill(vector<vector<int>> key)
{    
    for (int startR = 0; startR <= wideLock.size() - keyR; ++startR)
    {
        for (int startC = 0; startC <= wideLock[0].size() - keyC; ++startC)
        {
            bool success = Check(startR, startC, key);
            
            if (success)
                return true;
        }
    }
    
    return false;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = true;
    
    keyR = key.size(), keyC = key[0].size();
    lockR = lock.size(), lockC = lock[0].size();
    
    // 확장된 자물쇠를 만드는 과정
    wideLock.resize((lockR + keyR + keyR) - 2, vector<int>((lockC + keyC + keyC) - 2, -1));
        
    for (int r = 0, wideR = keyR - 1; r < lockR; ++r, ++wideR)
    {
        for (int c = 0, wideC = keyC - 1; c < lockC; ++c, ++wideC)
        {
            wideLock[wideR][wideC] = lock[r][c];
            
            // 만약 홈이라면 홈의 개수를 증가시킨다.
            if (lock[r][c] == 0)
                ++blankNum;
        }
    }
    
    // 키의 모양이 정사각형이기에
    // 4번 회전하면 원래대로 돌아온다.
    // 그렇기에 4번 반복한다.
    for (int i = 0; i < 4; ++i)
    {
        answer = CanFill(key); 
        
        if (answer == true)
            break;              // 만약 현재 키로 자물쇠의 모든 홈을 매울 수 있는 경우
        else
            key = Rotate(key);  // 못 매울 경우 회전시킨다.
    }
    
    
    return answer;
}

 

---

전에 참고했었던 풀이

https://yabmoons.tistory.com/678