2020 KAKAO BLIND RECRUITMENT - 3. 자물쇠와 열쇠

programmers.co.kr/learn/courses/30/lessons/60059

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

카카오 3번 문제.

코딩 꼬꼬마시절(지금은 유년기 정도 되는 것 같다.) 2019년에 무턱대고 카카오 시험 보다가 좌절했던 문제이다. 강해져서 돌아왔으니 혼내주도록하자. 이래놓고 사실 내가 3시간 넘게 혼났다.

이 문제는 발상이 중요한 문제같다.

자물쇠와 키가 최소한으로 겹쳤을 때까지 커버할 수 있도록 board의 사이즈를 2 * (key 사이즈 - 1) + 자물쇠 사이즈로 두고 가능한 모든 키와 자물쇠의 조합(키 회전 + 이동)을 완전탐색하여 문제를 해결하였다. 

#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<int>> vvi;

void rotate(vvi& key) {
	int m = key.size();
	vvi tmp(m, vector<int>(m, 0));
	for (int y = 0; y < m; y++) {
		for (int x = 0; x < m; x++) {
			tmp[m - x - 1][y] = key[y][x];
		}
	}
	key = tmp;
}

bool check_key(vvi& key, vvi& board, int n, int m, int s_idx) {
	bool correct = 1;
	
	//key 배열의 우하단 (m - 1, m - 1) 지점이 board의 (s_idx, s_idx)와 일치하는 경우부터
	//key 벡터의 좌상단 (0, 0) 지점이 (s_idx + n - 1, s_idx + n - 1)와 일치하는 경우까지 키를 한 칸씩 이동
	for (int y = s_idx - (m - 1); y < s_idx + n; y++) {
		for (int x = s_idx - (m - 1); x < s_idx + n; x++) {
			//insert key
			for (int ky = y; ky < y + m; ky++) {
				for (int kx = x; kx < x + m; kx++) {
					board[ky][kx] += key[ky - y][kx - x];
				}
			}
			//check correct
			for (int y = s_idx; y < s_idx + n; y++) {
				for (int x = s_idx; x < s_idx + n; x++) {
					if (board[y][x] != 1) {
						correct = 0;
						break;
					}
				}
			}
			if (correct) return true;
			//delete key
			for (int ky = y; ky < y + m; ky++) {
				for (int kx = x; kx < x + m; kx++) {
					board[ky][kx] -= key[ky - y][kx - x];
				}
			}
			correct = 1;
		}
	}
	return false;
}

bool solution(vvi& key, vvi& lock) {
	vvi board;
	int n, m, s_idx;

	n = lock.size();
	m = key.size();

	//lock과 1줄만 겹치도록 key를 집어 넣을 수 있도록 board의 크기를 잡아준다.
	board.resize(2 * m + n - 2, vector<int>(2 * m + n - 2, 0));
	s_idx = m - 1;

	//insert lock
	//board의 (s_idx, s_idx)에 lock의 (0, 0)이 위치
	for (int y = s_idx; y < s_idx + n; y++) {
		for (int x = s_idx; x < s_idx + n; x++) {
			board[y][x] = lock[y - s_idx][x - s_idx];
		}
	}

	for (int k = 0; k < 4; k++) {
		rotate(key);
		if (check_key(key, board, n, m, s_idx)) return true;
	}
	return false;
}

int main() {
	vvi key;
	vvi lock;
	int n, m, tmp;
	cin >> m >> n;
	key.resize(m, vector<int>(m, 0));
	lock.resize(n, vector<int>(n, 0));
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			cin >> key[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> lock[i][j];
		}
	}
	cout << solution(key, lock) << '\n';
	return 0;
}