[프로그래머스/C++] 자물쇠와 열쇠 (2020 KAKAO BLIND RECRUITMENT)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 열쇠로 자물쇠를 열 수 있는지 확인하는 문제다.

여기서 중요한 점은 열쇠의 블럭과 자물쇠의 블럭이 일치해야 하는데, 만약 열쇠의 블럭이 있는 부분이 자물쇠에 블럭이 있는 부분이라면 열지 못한다는 점이다. 

 

그러므로 열쇠와 자물쇠가 정확히 일치해야 하는데, 자물쇠 밖에 있는 열쇠의 범위는 블럭이 있어도 되고 없어도 된다는게 특징이다.

 

그래서 문제를 풀 때 열쇠의 오른쪽 하단이 자물쇠 왼쪽 상단부터 시작해 전부 탐색하는 방식으로 코드를 구현했다.

위 그림에 보이는 것처럼 열쇠와 자물쇠가 겹치는 최소 범위부터 시작해 왼쪽으로 이동하고, 자물쇠의 가장 왼쪽과 열쇠의 가장 오른쪽이 겹치면 한칸 아래로 내려 다시 옆으로 비교를 하는 식으로 코드를 구현했다.

 

여기서 위에 보이는 sy, sx와 ey, ex는 열쇠의 범위를 나타내는 변수다.

 

sy, sx와 ey, ex를 이용해 비교하는 것은 아래 그림을 참고하자

이 그림에서 자물쇠의 i, j 부분에 열쇠를 비교한다고 생각하자.

 

그러면 열쇠의 sy, sx부분이 이 i, j를 의미한다.

그리고 ey, ex는 sy, sx에서 열쇠의 크기(size) 만큼 더한 범위다.

 

그러므로 자물쇠를 열 수 있는지 탐색할 때, [a, b] 지점이 (sy <= a <= ey, sx <= b <= ex)를 만족한다면, 자물쇠와 열쇠가 겹친 부분이므로 둘을 비교해야하는 부분이다.

 

여기서 둘을 비교할 때, 자물쇠의 i, j 부분 즉, sy, sx 부분을 열쇠의 0, 0과 비교해야 하므로

열쇠의 비교할 부분은 (i-sy, j-sx)로 나타낼 수 있게 된다.

자물쇠를 탐색하는 부분이 (sy <= a <= ey, sx <= b <= ex)를 만족 할 때만 비교!

 

코드에서 compare 함수가 자물쇠와 열쇠를 비교하는 것을 구현한 함수다.

CanOpen 함수는 열쇠가 옆과 아래로 이동하는 것을 구현한 함수다.

 

열쇠로 자물쇠가 겹치는 부분과 안겹치는 부분을 비교를 하는 방법은 아래와 같다.

 

1. 자물쇠의 모든 칸을 탐색할 때, 자물쇠가 열리기 위해서는 열쇠와 겹치지 않은 자물쇠의 부분은 전부 1을 나타내야한다.

2. 열쇠와 자물쇠가 겹치는 부분은 둘 중 하나는 0, 나머지 하나는 1이여야한다.

  (둘 다 1이거나 0인 경우는 열 수 없는 경우다.)

 

이렇게 탐색을 하면서 자물쇠가 열리면 자물쇠를 열 수 있으므로 true를 return하면 된다.

 

만약 자물쇠가 열리지 않았다면 열쇠를 시계방향으로 돌린 뒤, 다시 자물쇠의 왼쪽 상단부터 완전 탐색을 하면 된다.

 

[아이디어 정리]

1. 열쇠의 오른쪽 하단과 자물쇠의 왼쪽 상단이 겹치는 부분부터 시작해 자물쇠에 열쇠가 들어갈 수 있는 모든 경우를 완전 탐색한다.
2. 완전 탐색 결과 열리지 않는다면, 열쇠를 시계 방향으로 돌려 다시 완전 탐색한다.
3. 중간에 자물쇠가 열리면 true를 반환하고, 만약 모든 경우가 열리지 않으면 false를 반환한다.

 

 

Code

 

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

vector<vector<int>> rotate(vector<vector<int>> key) // 시계방향 회전
{
    int y=key.size(); 
    vector<vector<int>>nv(y,vector<int>(y,0));
    for (int i=0; i<y; i++)
    {
        for (int j=0; j<y; j++)
        {
            nv[j][y-(i+1)]=key[i][j];
        }
    }
    return nv;
}

bool compare(int sy, int sx, int ey, int ex, vector<vector<int>>& key, vector<vector<int>>& lock)
{ // ky는 ly와 비슷하게 시작하는 지점임
    int y= lock.size();
    for (int i=0; i<y; i++)
    {
        for (int j=0; j<y; j++)
        {
            if (sy<=i&&i<=ey&&sx<=j&&j<=ex)
            {
                if (lock[i][j]==0)
                {
                    if (key[i-sy][j-sx]==0)
                    {
                        return false;
                    }
                }
                else
                {
                    if (key[i-sy][j-sx]==1)
                    {
                        return false;
                    }
                }
            }
            else
            {
                if (lock[i][j]==0) 
                {
                    return false;
                }
            }
        }
    }
    return true;
}

bool CanOpen(vector<vector<int>> &key, vector<vector<int>> &lock)
{
    int kY=key.size(),lY=lock.size();
    //(int sy, int sx, int ey, int ex, vector<vector<int>> key, vector<vector<int>> lock)
    for (int i=0; i<kY+lY-1; i++)
    {
        for (int j=0; j<kY+lY-1; j++)
        {
            if (compare(i-kY+1,j-kY+1,i, j,key, lock))
            {
                return true;
            }              
        }
    }        
    for (int k=0; k<4; k++)
    {
        key=rotate(key);        
        for (int i=0; i<kY+lY-1; i++)
        {
            for (int j=0; j<kY+lY-1; j++)
            {
                if (compare(i-kY+1,j-kY+1,i, j,key, lock))
                {
                    return true;
                }          
            }
        } 
    }
    return false;
}


bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    // 400 번 반복 * 4 * 상하좌우 800
    return CanOpen(key, lock);
}

---

이 문제는 특별한 알고리즘이나 아이디어가 어려운 문제는 아니였다.

아마 완전 탐색을 직접 구현하는게 조금 귀찮은 문제였던 것 같다.

그림을 그릴 종이가 있다면 구현 난이도가 엄청 쉬워지는 문제...

 

프로그래머스