[프로그래머스 2020 KAKAO BLIND RECRUITMENT] 자물쇠와 열쇠

문제

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

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

 

문제 풀이

 

처음엔 열쇠를 따로 벡터에 넣어 관리하며 열쇠의 상태를 방문처리하는 방법으로 bfs를 돌려볼까 했으나 생각보다 구현이 힘들것 같아 다른 방향으로 생각해봤다.

---

•  키를 상,하,좌,우로 움직이는 경우를 생각해보면 아래와 같이 왼쪽 위 끝부터 오른쪽 아래 끝까지 이동할 수 있다.

 

•  키를 최대 $(n + m - 1)^2$번 이동하고 4번 회전할 수 있으며 lock의 개수 $(m^2)$만큼 비교하므로 충분히 완전탐색으로 구현할 수 있었다. $O(4*(n+m-1)^2*(m^2))$
  
  

•  배열의 끝을 잘 생각하며 구현해야해서 생각보다 까다로웠다..

어떻게 구현?

 

1. 키를 회전하는 함수작성 

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

 

2. 키와 자물쇠를 비교할 수 있을 만큼 큰$(n*2*m-2)^2$ 배열grid에 자물쇠 상태 저장

    for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!lock[i][j]) k++; // k = 자물쇠 홈의 개수
			else grid[m - 1 + i][m - 1 + j] = lock[i][j]; // 그리드 중앙에 lock을 저장
		}
	}

 

3. 키를 이동,회전하며 lock에 비교

// (i,j) = 그리드 내부 키의 시작(왼쪽 위 끝)좌표, (r,c) = 키 배열의 인덱스
// (r + i, c + j) = lock의 좌표
for (int i = 0; i < m + n - 1; i++) {
		for (int j = 0; j < m + n - 1; j++) {
			for (int dir = 0; dir < 4; dir++) {
				int num = 0, flag = 0;
				for (int r = 0; r < m; r++) {
					for (int c = 0; c < m; c++) {
						if (!key[r][c]) continue;
						if (r + i >= m - 1 && r + i <= n + m - 2&& c + j >= m - 1 && c + j <= n + m - 2) {
							if (!grid[r + i][c + j]) num++;
							else flag = 1; //  열쇠의 돌기와 자물쇠의 돌기가 만나는 경우
						}
					}
				}
				if (!flag && num == k) return 1;
				rotate(key);
			}
		}
	}

 

코드

#include <string>
#include <vector>

using namespace std;

int grid[440][440], tmp[21][21], n, m, k;

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

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	n = lock.size(), m = key.size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!lock[i][j]) k++;
			grid[m - 1 + i][m - 1 + j] = lock[i][j];
		}
	}
	for (int i = 0; i < m + n - 1; i++) {
		for (int j = 0; j < m + n - 1; j++) {
			for (int dir = 0; dir < 4; dir++) {
				int num = 0, flag = 0;
				for (int r = 0; r < m; r++) {
					for (int c = 0; c < m; c++) {
						if (!key[r][c]) continue;
						if (r + i >= m - 1 && r + i <= n + m - 2&& c + j >= m - 1 && c + j <= n + m - 2) {
							if (!grid[r + i][c + j]) num++;
							else flag = 1;
						}
					}
				}
				if (!flag && num == k) return 1;
				rotate(key);
			}
		}
	}
	return 0;
}