[프로그래머스] 자물쇠와 열쇠

프로그래머스 자물쇠와 열쇠 풀이입니다.

이 문제는 완전탐색 시뮬레이션이다.

하지만 배열을 회전시키고 또 확장 시키는 것이 어색하다면 풀기 굉장히 어려운 문제가 될 수 있다.

접근법은 간단하다. 키를 회전시키면서 이동시켜가며 자물쇠와 모든 부분이 맞물리는지 확인하고 맞물리는게 확인되면 true를 리턴하고 아니면 false를 리턴시키면 된다.

Problem : 자물쇠와 열쇠

Source Code(C++) :

#include <string>
#include <vector>

using namespace std;

int CNT, M, N;

void Rotate(vector<vector<int>>& key) { // 90도 회전 
	vector<vector<int> > tmp(M, vector<int>(M, 0));
	for (int i = 0; i < M; i++)
		for (int j = 0; j < M; j++)
			tmp[j][M - i - 1] = key[i][j];
	key = tmp;
}


bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	M = key.size();
	N = lock.size();

	bool result = true;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (lock[i][j] == 0)
				CNT++; // 홈 갯수 

	for (int rotate = 0; rotate < 4; rotate++) {
		for (int i = -20; i <= 20; i++) {
			for (int j = -20; j <= 20; j++) {
				int cnt = 0;
				result = false;
				for (int x = 0; x < M; x++) {
					for (int y = 0; y < M; y++) {
						int nx = x + j;
						int ny = y + i;
						if (0 <= ny && ny < N && 0 <= nx && nx < N) {
							if (lock[ny][nx] == 1 && key[y][x] == 1) result = true;
							else if (lock[ny][nx] == 0 && key[y][x] == 1) cnt++;
						}
					}
				}
				if (cnt == CNT && !result) return true;
			}
		}
		Rotate(key);
	}


	return false;
}

소스코드

이 외에도 제가 푼 문제들 소스코드는 다음 링크에 있습니다!!! 알고리즘 문제풀이