[cpp]자물쇠와 열쇠 - 2020 카카오 블라인드 채용

고고학자인 “튜브”는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

 

 

---

 

 삼성느낌이 나는 구현 문제였습니다. 열쇠를 돌려서 자물쇠에 넣어보는데, 열쇠가 자물쇠 영역을 벗어나도 된다는 특징을 가지고 있는 문제입니다. 이걸 어떻게 처리하는지 아이디어를 내는 것이 이 문제의 핵심이라고 생각합니다. 저는 key와 lock의 입력이 모두 20으로 작아서 거대한 정사각형에 key와 lock을 이어붙이고 완전탐색을 하는 방법을 택했습니다.

 

m은 key의 한 행의 크기, n은 lock의 한 행의 크기입니다.

 

1. MapInit

int MapInit(vector<vector<int>> lock, int m, int n) {
	int padding = m - 1, sSize = n + padding * 2;
	for (int i = padding; i < padding + n; ++i) {
		for (int j = padding; j < padding + n; ++j) {
			board[i][j] = lock[i - padding][j - padding];
		}
	}
	return sSize;
}

 

 알고리즘에서 사용할 열쇠와 자물쇠를 합친 board의 크기를 구하는 함수입니다. 저는 거대한 정사각형(거정이라고 부르겠습니다) 중앙에 lock을 넣고, 거정의 영역 안에서 열쇠를 옮겨 해가 있는지 판단하려고 하였고, 이때 열쇠는 무조건 자물쇠와 적어도 1칸 이상 겹쳐야 하기 때문에 자물쇠의 한 변에서 거정의 한 변까지의 길이인 padding은 m-1로 정의하였습니다. (아래 사진을 참고바랍니다) 이 거정의 변의 길이는 자물쇠의 크기 n + padding * 2 로 구할 수 있습니다. 이후 거정의 가운데 자물쇠 값을 넣어주고 거정의 한 변의 길이를 리턴하였습니다.

 

 

2.KeyInput

bool KeyInput(vector<vector<int>> key, int i, int j, int m, int sSize) {
    for (int a = i; a < i + m; ++a) {
        for (int b = j; b < j + m; ++b) {
            if (key[a - i][b - j] == 0) continue;
            if (tmpBoard[a][b] == 1 && key[a - i][b - j] == 1) return false;
            tmpBoard[a][b] = key[a - i][b - j];
        }
    }
    return true;
}

이후 거정의 좌측 상단부터 완전탐색 방식으로 모든 좌표에 키를 꽂아봅니다. 이때 자물쇠와 열쇠의 돌기가 일치하는 부분이 없는지 판단하는 함수가 KeyInput입니다. 만약 같은 좌표에서 자물쇠와 열쇠 모두 돌기인 경우 false를 리턴합니다. 만약 모든 부분에서 좌물쇠와 열쇠의 돌기가 겹친 부분이 없는 경우, 그때의 열쇠 정보를 거정에 입력한 뒤 true를 리턴합니다. 나중에 이 정보를 이용하여 자물쇠의 모든 홈 부분을 채웠는지 판단합니다.

 

3.KeyInput

int Check(int m, int n) {
	int padding = m - 1;

	for (int i = padding; i < padding + n; ++i) {
		for (int j = padding; j < padding + n; ++j) {
			if (tmpBoard[i][j] == 0) return false;
		}
	}
	return true;
}

2번에서 열쇠를 꽂은 데이터인 tmpBoard를 기준으로, 자물쇠 영역을 체크해 꽉 찬경우(모든 셀이 0이 아닌 경우) true를 리턴하고 프로그램을 종료합니다.

 

4. 4방향 Rotate

void Rotate(vector<vector<int>> &key, int m) {
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < m; ++j)
			keyTmp[i][j] = key[m - j - 1][i];
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < m; ++j)
			key[i][j] = keyTmp[i][j];
}

이 문제에서 열쇠는 4방향으로 돌릴 수 있습니다. 비슷한 문제 잘 풀고싶으면 2차원 배열 돌리는 코드는 외워두는게 좋습니다. 위 코드대로 열쇠를 4방향으로 돌리면 아래처럼 출력됩니다.

 

 

전체코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int board[63][63];
int tmpBoard[63][63];
int keyTmp[21][21];

int MapInit(vector<vector<int>> lock, int m, int n) {
	int padding = m - 1, sSize = n + padding * 2;
	for (int i = padding; i < padding + n; ++i) {
		for (int j = padding; j < padding + n; ++j) {
			board[i][j] = lock[i - padding][j - padding];
		}
	}
	return sSize;
}

int Check(int m, int n) {
	int padding = m - 1;

	for (int i = padding; i < padding + n; ++i) {
		for (int j = padding; j < padding + n; ++j) {
			if (tmpBoard[i][j] == 0) return false;
		}
	}
	return true;
}

void TmpInit(int sSize) {
	for (int i = 0; i < sSize; ++i) {
		for (int j = 0; j < sSize; ++j) {
			tmpBoard[i][j] = board[i][j];
		}
	}
}

bool KeyInput(vector<vector<int>> key, int i, int j, int m, int sSize) {
	for (int a = i; a < i + m; ++a) {
		for (int b = j; b < j + m; ++b) {
			if (key[a - i][b - j] == 0) continue;
			if (tmpBoard[a][b] == 1 && key[a - i][b - j] == 1) return false;
			tmpBoard[a][b] = key[a - i][b - j];
		}
	}
	return true;
}

void Rotate(vector<vector<int>> &key, int m) {
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < m; ++j)
			keyTmp[i][j] = key[m - j - 1][i];
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < m; ++j)
			key[i][j] = keyTmp[i][j];
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	bool answer = false;
	int m = key.size(), n = lock.size();
	int sSize = MapInit(lock, m, n);

	for (int k = 0; k < 4; ++k) {
		for (int i = 0; i < sSize -m + 1; ++i) {
			for (int j = 0; j < sSize - m + 1; ++j) {
				TmpInit(sSize);
				if (!KeyInput(key, i, j, m, sSize)) continue;
				if (Check(m, n)) return true;
			}
		}
		Rotate(key, m);
	}
	return false;
}

 

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