프로그래머스 Level 3 자물쇠와열쇠

자물쇠와열쇠 (프로그래머스 Level 3)

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

이전처럼 구현에 굉장히 많은 시간을 소요한 문제이다
처음에는 ‘이동’을 구현할 때
실제로 key에 해당하는 배열의 side 부분을 0 으로 밀어버리는 방식을 채택하였으나
해당 방식으로는 ‘서로 같지 않은 크기’에서
잘못된 key를 만들 수 있다는 점을 깨닫고
테두리에 해당하는 새로운 배열을 생성하는 방식으로 문제를 해결하였다
ex)
key.size()가 3이라면 3 3 3
3 lock 3
3 3 3
이런식으로 공백의 열을 만들어준 후
해당하는 새로운 배열에서
‘key’에 해당하는 1을 삽입하였을때
lock에 해당하는 부분이 모두 1이 되었는지를 체크하는 방식으로 문제를 풀 수 있었다

문제의 구현 중 까다로웠던 부분은
‘회전’을 구현하는 방식 과
‘똑같은 key’가 이미 확인되었는지를 파악하기 였던것 같다

‘회전’을 구현하는 방식은
0,0 0,1 0,2 -> 2,0 1,0 0,0
1,0 1,1 1,2 -> 2,1 1,1 0,1
2,0 2,1 2,2 -> 2,2 1,2 0,2
로 바뀌는 방식으로

해당 알고리즘이 성립한다

	for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				// 중앙을 기준으로 90도 회전
				result[j][n - 1 - i] = matrix[i][j];
			}
		}

이후
같은 key가 확인되었는지는 set으로 확인하여 파악하였다

사실 매우 많은 hint를 보고 푼 문제이기도 하다
대표적으로 ‘90도 회전’을 실제로 어떻게 구현해야 할지 막막하였다
추가적으로 ‘이동’에 대한 부분도 힌트를 보고 해결하기도 하였다
실제로 이 문제를 제한 시간내에 힌트 없이 풀 수 있을지 잘 모르겠다

Code

#include <vector>
#include <set>
#include<queue>
using namespace std;

// 2D 벡터를 90도 회전시키는 함수
vector<vector<int>> rotate90(const vector<vector<int>>& matrix) {
    int n = matrix.size(); // 행렬의 크기
    vector<vector<int>> result(n, vector<int>(n)); // 결과 행렬 초기화

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 중앙을 기준으로 90도 회전
            result[j][n - 1 - i] = matrix[i][j];
        }
    }

    return result;
}

// 해당 key가 정답인지 확인
bool isKeyRight(const vector<vector<int>>& key, const vector<vector<int>>& lock)
{
    const int keySize = key.size();
    const int lockSize = lock.size();

    for (int i = 0; i < lockSize; i++)
    {
        for (int j = 0; j < lockSize; j++)
        {
            if (i + keySize <= lockSize &&
                j + keySize <= lockSize)
            {
                vector<vector<int>> temp(lock);

                bool isFind = true;

                for (int a = 0; a < keySize; a++)
                {
                    for (int b = 0; b < keySize; b++)
                    {
                        if (temp[i + a][j + b] == 0 &&
                            key[a][b] == 1)
                        {
                            temp[i + a][j + b] = 1;
                        }
                        else if (temp[i + a][j + b] == 1 &&
                            key[a][b] == 1)
                        {
                            isFind = false;
                            break;
                        }
                    }

                    if (isFind == false)
                        break;
                }

                for (int i = keySize; i < lockSize - keySize; i++)
                {
                    for (int j = keySize; j < lockSize - keySize; j++)
                    {
                        if (temp[i][j] != 1)
                        {
                            isFind = false;
                            break;
                        }
                    }
                    if(isFind == false)
                        break;
                }
                
                if (isFind == true)
                    return true;
            }
        }
    }

    return false;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    // set에 넣어서 중복 확인하기
    set <vector<vector<int>>> keySet;
    const int kSize = key.size();
    const int lSize = lock.size();
    
    vector<vector<int>> newLock(lSize + kSize * 2, vector<int>(lSize + kSize * 2, 0));
    for (int i = kSize, a = 0; i < lSize + kSize; i++,a++)
    {
        for (int j = kSize, b = 0; j < lSize + kSize; j++,b++)
        {
            newLock[i][j] = lock[a][b];
        }
    }

    queue < vector<vector<int>> >q;
    q.push(key);

    while (q.empty() == false)
    {
        auto nowKey = q.front();
        q.pop();

        // 이미 찾은 키
        if (keySet.find(nowKey) != keySet.end())
        {
            continue;
        }

        if (isKeyRight(nowKey, newLock))
        {
            return true;
        }

        keySet.insert(nowKey);

        auto rV = rotate90(nowKey);
        q.push(rV);
        rV = rotate90(rV);
        q.push(rV);
        rV = rotate90(rV);
        q.push(rV);
    }

    return false;
}