[구현 알고리즘] 자물쇠와 열쇠 ★★☆

기출 : 2020 카카오 신입 공채

 

문제 자체는 어렵지 않았는데 구현에 대한 경험이 부족하다면 좀 까다롭게 느낄 수 있는 문제였다

 

문제의 아이디어는 정말 간단하다

 

열쇠를 회전하면 총 4가지의 패턴이 나오고 각 패턴에 대해서 자물쇠에 하나씩 대 보는 것이다

 

구현 자체가 어려운 문제들, 즉 피지컬을 필요로 하는 문제들을 풀 때 항상 해야 하는 것이 있다

 

먼저 문제를 큰 덩어리로 구분하고 각 덩어리를 pseudo code로 작성하는 것이다

 

작성한 pseudo code는 다음과 같다

for 회전하여 만든 모든 열쇠 패턴에 대하여
	for 열쇠를 상하좌우로 이동하며
    	if(check()) return true;	자물쇠에 대보고 맞으면 true return
return false	모든 경우의 수를 확인한 뒤 return false

 

그 다음으로 해야 할 것은 회전하기, 자물쇠에 대보기 함수를 작성하는 것이 될 것이다

---

회전하기 함수

 

회전하기 함수를 작성할 땐 좌표를 먼저 쭉 적어보는 것이 도움이 된다

 

(x,y) 좌표가 어떤 좌표로부터 왔는가를 확인해야 하므로 이를 적어보면 다음과 같다

 

(0,0) : (2,0) 에서

(0,1) : (1,0) 에서

(0,2) : (0,0) 에서

(1,0) : (2,1) 에서

(1,1) : (1,1) 에서

 

이로부터 규칙성을 확인하면 (x,y)는 (m-(y+1),x) 로부터 온 것을 확인할 수 있다

 

이를 코드로 작성하면 다음과 같다

vector<vector<int>> rot(vector<vector<int>> key) {
    vector<vector<int>> tmpkey;
    for (int i = 0;i < m;i++) {
        vector<int> tmpv;
        for (int j = 0;j < m;j++) tmpv.push_back(key[m - (1 + j)][i]);
        tmpkey.push_back(tmpv);
    }
    return tmpkey;
}

---

자물쇠에 대보기 함수

 

자물쇠에 대보는 것은 간단하다

 

모든 자물쇠 좌표에 대해서 이동된 열쇠의 좌표를 비교해보면 된다

 

이동된 열쇠의 좌표가 자물쇠를 벗어나는 경우는 검사하지 않고

 

열쇠가 자물쇠 구멍이 아닌 부분을 차지하거나 자물쇠의 구멍이 비어있는데 열쇠가 해당 부분에 없는 경우는 제외한다

 

자물쇠 구멍이 난 부분에 열쇠가 들어가는 상황을 체크하고 열쇠의 구멍 개수를 카운트하여 성공 여부를 판단한다

 

말보다 코드를 보는 것이 더 이해가 빠를 것이다

bool check(int x, int y, vector<vector<int>>& key, vector<vector<int>>& lock) {
    int cnt = 0;
    for (int i = 0; i < n;i++) {
        for (int j = 0;j < n;j++) {
            if (i - x < 0 || j - y < 0 || i - x >= m  || j - y >= m) continue;
            if (key[i - x][j - y] == 0 && lock[i][j] == 0) return false;
            if (key[i - x][j - y] == 1 && lock[i][j] == 1) return false;
            if (key[i - x][j - y] == 1 && lock[i][j] == 0) cnt++;
        }
    }
    if (hole == cnt) return true;
    else return false;
}

---

이 두가지 핵심 함수를 작성한 뒤 solution함수를 작성하면 다음과 같다

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            if (lock[i][j] == 0) hole++;
        }
    }
    for (int i = -(m - 1);i <= (n - 1);i++) {
        for (int j = -(m - 1);j <= (n - 1);j++) {
            cout << "(" << i << "," << j << ") checking\n";
            if (check(i, j, key, lock)) return true;
            else    cout << "(" << i << "," << j << ") checked\n";
        }
    }
    for (int i = 0;i < 3;i++) {
        key = rot(key);
        for (int i = -(m - 1);i <= (n - 1);i++) {
            for (int j = -(m - 1);j <= (n - 1);j++) {
                cout << "(" << i << "," << j << ") checking\n";
                if (check(i, j, key, lock)) return true;
                else cout << "(" << i << "," << j << ") checked\n";
            }
        }
    }
    return false;
}