[C++로 풀이] 자물쇠와 열쇠 (완전 탐색)⭐⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 자물쇠와 열쇠
난이도 ⭐⭐⭐
🚀 문제
🚀 내 풀이 ⭕
✈ 1 차 풀이 ❌ (DFS) (작성하다 말았던 코드입니다.)
// 💚현재 모습에서 시계방향 90도로 회전시키기 (pos에 1의 위치를 기록)💚
void rotate(int m, vector<pair<int, int>>& pos) {
for (int i = 0; i < pos.size(); i++) {
int temp_row = pos[i].first;
int temp_col = pos[i].second;
pos[i].first = temp_col;
pos[i].second = m - 1 - temp_row;
}
}
// ⭐🌈 DFS 로 현재의 key의 "회전된 모습"에서 상하좌우 모든 이동 조합 구해나가기. lock의 홈과 완전히 일치하면 종료 🌈⭐
void DFS(vector<pair<int, int>>& keywayPos, int& keyway, vector<vector<int>> key, bool& answer, int dir) {
// 이동
for (int i = 0; i < key.size(); i++) {
for (int j = 0; j < key.size(); j++) {
/* 1️⃣ "상" 이동 */
// 👉 1. 이동시키기(key의 1값 전부 위로 한칸씩 이동)
// 2. lock 과 일치하는지 검사
// 3. 일치하면 answer = ture 후 종료하고 일치하지 않다면 ⭐🌈 DFS 로 <다음 이동>하러가기 🌈⭐
/* 2️⃣ "하" 이동 */
// 👉 1. 이동시키기(key의 1값 전부 아래로 한칸씩 이동)
// 2. lock 과 일치하는지 검사
// 3. 일치하면 answer = ture 후 종료하고 일치하지 않다면 ⭐🌈 DFS 로 <다음 이동>하러가기 🌈⭐
/* 3️⃣ "좌" 이동 */
// 👉 1. 이동시키기(key의 1값 전부 왼쪽으로 한칸씩 이동)
// 2. lock 과 일치하는지 검사
// 3. 일치하면 answer = ture 후 종료하고 일치하지 않다면 ⭐🌈 DFS 로 <다음 이동>하러가기 🌈⭐
/* 4️⃣ "우" 이동 */
// 👉 1. 이동시키기(key의 1값 전부 오른쪽로 한칸씩 이동)
// 2. lock 과 일치하는지 검사
// 3. 일치하면 answer = ture 후 종료하고 일치하지 않다면 ⭐🌈 DFS 로 <다음 이동>하러가기 🌈⭐
}
}
return;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock){
bool answer = false;
int m = key.size(); // m X m
int n = lock.size(); // n X n
// 1️⃣ key의 크기가 lock과 동일해지도록 (n x n) key에 살을 붙인다.
for (int i = 0; i < m; ++i) {
while (key[i].size() < n) {
key[i].push_back(0);
}
}
while (key.size() < n) {
vector<int> v(n, 0);
key.push_back(v);
}
// 2️⃣ key의 1의 위치들 저장 (= 돌기의 위치)
vector<pair<int, int>> bumpPos;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (key[i][j] == 1)
bumpPos.push_back(make_pair(i, j));
// 3️⃣ lock의 0의 위치들 저장 (= 홈의 위치)
vector<pair<int, int>> keywayPos;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (lock[i][j] == 1)
keywayPos.push_back(make_pair(i, j));
// 4️⃣ "회전"은 4가지뿐 ! 회전 별로 상하좌우 "이동"의 모든 조합은 DFS로
// key 를 각각 4가지로 회전해본 후 회전 별로 상하좌우 이동 모든 조합을 DFS로 검사해서 key의 돌기(1)가 lock의 홈(0)과 일치할 때를 찾으면 DFS 종료하도록
for (int i = 0; i < 4; ++i) { // 4가지의 회전 (0 : 회전 X, 1 : 90도 회전, 2 : 180도 회전, 3 : 270도 회전)
if (i != 0) {
for (int j = 0; j < n; j++)
fill(key[j].begin(), key[j].end(), 0); // 회전 전 0으로 모두 초기화
rotate(n, bumpPos); // 회전시키기 (bumPos에 기록, 즉 새로운 돌기 위치 기록)
for (int j = 0; j < bumpPos.size(); j++) // 회전된 새로운 bumPos에 따라 돌기 위치마다 1 대입
key[bumpPos[j].first][bumpPos[j].second] = 1;
}
if (answer == false)
//⭐🌈 DFS 로 이동하러가기 🌈⭐
}
}
DFS 풀이로 위와 같은 코드를 작성하다가 너무 복잡해서 이건 아니다 싶어 포기했다..😅 중도 포기했어서 미완성 코드이긴 하지만 대충 위와 같은 로직으로 작성했었다.
key를 4가지로 회전 (0도, 90도, 180도, 270도. 회전에 대한 설명은 아래..)- 👉 이 각각의 회전마다 “이동 DFS” 진행. 상,하,좌,우 이렇게 4가지의 조합으로 이동을 진행하게 된다.
- 그러다 DFS에서
lock의 모든 홈과key의 모든 돌기가 일치할 때,key의 돌기가lock의 돌기와 일치하지 않을 때 자물쇠와 열쇠가 맞는 경우를 찾은 것이므로answer를 true로 만들고 DFS 모두 종료.
- 그러다 DFS에서
- 👉 이 각각의 회전마다 “이동 DFS” 진행. 상,하,좌,우 이렇게 4가지의 조합으로 이동을 진행하게 된다.
원래 이와 같은 로직으로 짜는게 내 계획이었다. 근데 key를 이동하는 것을 구현하는게 문제였다. 상, 하, 좌, 우마다 한 칸씩 이동할 때 위로 이동할 땐 첫 행 제외 모든 행들을 위로 한칸씩 올려줘야 하고 우로 이동할 땐 첫 행 제외 모든 행들을 오른쪽으로 한 칸씩 밀어줘야 하고.. 또 이중 반복문의 진행은 위에서 아래 행으로, 왼쪽에서 오른쪽 열로 순회하기 때문에 이렇게 한 칸씩 밀 경우 다음에 순회해야 할 곳이 미리 덮어 씌워질 수 있는 아래쪽과 오른쪽은 어떻게 이동 처리를 해야할지 갑갑했다. 😭😭 또한 이렇게 한 칸씩 전부 밀어주어야 하니까 매 DFS 단계마다 O(n^2)이 된다는 얘기와도 같았기 때문에 이렇게 DFS 로 풀면 안되겠다는 생각이 들어 코드를 쓰다가 중단하였다.
✈ 2 차 풀이 ⭕ (일치하는 경우를 찾는 새로운 방법)
#include <string>
#include <vector>
using namespace std;
// 현재 모습에서 시계방향 90도로 회전 한 모습으로 pos 에 새로운 1의 위치 기록
void rotate(int m, vector<pair<int, int>>& pos) {
for (int i = 0; i < pos.size(); i++) {
int temp_row = pos[i].first;
int temp_col = pos[i].second;
pos[i].first = temp_col;
pos[i].second = m - 1 - temp_row;
}
}
현재의 모습에서 시계방향으로 90도씩 회전시킬 때마다 위와 같은 규칙을 가지게 된다.
- (i, j) 좌표를 90도 회전시켰을 때
- 업뎃한
i👉 이전의j가 된다. - 업뎃한
j👉n - 1 - i가 된다. (업뎃 전i)
- 업뎃한
ex) n = 3 에서 2행 2열에 있는 원소를 90도 시계방향 회전시키면 2행 0열으로 옮겨져야 한다.
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
int n = lock.size();
int m = key.size();
vector<vector<int>> lockk(2 * m + n - 2, vector<int>(2 * m + n - 2));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
lockk[m - 1 + i][m - 1 + j] = lock[i][j];
vector<pair<int, int>> bumpPos;
for (int i = 0; i < m; i++)
for (int j = 0; j < m; j++)
if (key[i][j] == 1)
bumpPos.push_back(make_pair(i, j));
for (int i = 0; i < 4; i++) {
// 회전
if (i != 0) {
for (int j = 0; j < m; j++)
fill(key[j].begin(), key[j].end(), 0);
rotate(m, bumpPos);
for (int j = 0; j < bumpPos.size(); j++)
key[bumpPos[j].first][bumpPos[j].second] = 1;
}
// 좌상단
for (int j = 0; j < n + m - 1; j++) {
for (int k = 0; k < n + m - 1; k++) {
vector<vector<int>> tempLock(lockk);
for (int x = 0; x < m; x++){
for (int y = 0; y < m; y++) {
tempLock[j + x][k + y] += key[x][y];
}
}
bool flag = true;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (tempLock[m - 1 + i][m - 1 + j] != 1)
flag = false;
if (flag)
return true;
}
}
}
return false;
}
💡 전체 크기를 m - 1 + m - 1 + n 👉 2 * m + n - 2 로 늘리고 가운데에
lock을 배치한다.(lock의 좌상단이 (m-1, m-1) 좌표에 오게끔) 전체적으로 늘린 새로운 이 크기 안에서 4가지 회전한 모습 별로 `key`를 배치해보아 `lock`과 일치해질 때를 찾는다.
- 전체 크기
lockk👉 2 * m + n - 2 크기 (= m - 1 + m - 1 + n) 이름을 굉장히 못 지었지만 lockk 로 지었다. - 가운데에
lock이 온다. 👉 n 크기lock의 좌상단은lockk의 (m - 1, m - 1) 위치에 오게 된다.
key👉 m 크기lockk내에서 한칸씩 이동하면서 가운데 있는lock과 일치할 떄를 찾는다.key를 4가지 모습으로 회전하면서 찾는다.
위 사진의 경우 key는 총 (n + m - 1) ^ 2번, 즉 최대 5 x 5 = 25 번만 이동해보아도 key로 lock을 열 수 있는지 없는지를 판단할 수 있다. (key의 좌상단이 될 수 있는 경우가 25번이다.) key 4가지 회전별로 한번씩 살펴보므로 총! 최대 이동 횟수는 4 * 25 = 100 번 밖에 되지 않는다. 이 최대 비교 횟수 동안 한번도 lock과 일치하지 않았다면 결과는 false가 되는 것이다.
이 문제의 m과 n의 최대 크기는 각각 20이기 때문에 lockk의 최대 크기는 58 x 58 = 3364 가 된다. 그리고 총 비교 횟수는 4 x 39 x 39 = 6084 번 밖에 되지 않는다.
위 예제의 경우 key가 90도로 회전한 모습에서 19번 이동 했을 때 위와 같이 lock과 일치하는 것을 찾을 수 있다. (lockk 의 가운데 n x n 크기가 전부 1이 되야 함! 2나 0인게 하나라도 있으면 안된다.)
lock의 원소가 2가 된다는 것은 ->key의 돌기와lock의 돌기가 만났다는 것 (이러면 안됨. 돌기와 홈끼리만 맞아야함!)lock의 원소가 0이라는 것은 ->key도 홈이여서lock의 홈이 채워지지 않았다는 것.
따라서 lock의 원소가 모~두 1이 될 때, 그 key로 lock을 열 수 있는 것이다.
만약 key의 크기가 2라면 이런 모습이 될 것이고 (key가 lockk안에서 이동을 총 16번 할 수 있겠다.)
key의 크기가 1이라면 이런 모습이 될 것이다. key가 lock 안에서만 움직이면 되서 lockk은 lock과 동일한 크기일 것이다. 이 경우 9번만 움직여보면 찾을 수 있음!
int n = lock.size();
int m = key.size();
vector<vector<int>> lockk(2 * m + n - 2, vector<int>(2 * m + n - 2));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
lockk[m - 1 + i][m - 1 + j] = lock[i][j];
lockk을 (2 * m + n - 2) x (2 * m + n - 2) 사이즈로 선언.- (m - 1, m - 1) 좌표부터 가운데에 n x n 크기의
lock배치
- (m - 1, m - 1) 좌표부터 가운데에 n x n 크기의
vector<pair<int, int>> bumpPos;
for (int i = 0; i < m; i++)
for (int j = 0; j < m; j++)
if (key[i][j] == 1)
bumpPos.push_back(make_pair(i, j));
bumpPos에 key의 돌기 위치 저장
for (int i = 0; i < 4; i++) {
// 회전 (총 4가지)
if (i != 0) {
for (int j = 0; j < m; j++)
fill(key[j].begin(), key[j].end(), 0); // 한번 0 으로 모두 리셋 하고 (이전 회전 모습 지움)
rotate(m, bumpPos); // 지난 bumpPos 로 현재의 bumpPos에서 90도 회전한 것을 기준으로 한 새로운 bumpPos로 업데이트
for (int j = 0; j < bumpPos.size(); j++)
key[bumpPos[j].first][bumpPos[j].second] = 1; // 회전한 새로운 bumpPos로 key 값 업뎃
}
// 좌상단
for (int j = 0; j < n + m - 1; j++) {
for (int k = 0; k < n + m - 1; k++) {
vector<vector<int>> tempLock(lockk); // lockk을 복사해서 만든 tempLock 에다가 key 돌기 값을 더할 것.
// key 가 이동하면서 tempLock 에 원소 더하기
for (int x = 0; x < m; x++)
for (int y = 0; y < m; y++)
tempLock[j + x][k + y] += key[x][y]; // 맞물리는지 검사하기 위해 tempLock
bool flag = true;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (tempLock[m - 1 + i][m - 1 + j] != 1)
flag = false;
if (flag) // tempLock의 가운데 부분이 한번도 1이 아닌적이 없었다면, 즉 tempLock의 모든 원소가 1이라면
return true;
}
}
}
5 중 for문을 썼다. 세상에..! (그래도 시간 초과 안나고 충분하다.)
4가지 종류의 회전별로 0도, 90도, 180도, 270도 각각 회전한 모습 에서! (첫번째 for문) key가 lockk 내에서 이동할 수 있는 (n + m - 1) x (n + m - 1)번의 이동을 한 후 그때 그때마다 lockk의 가운데!! ((m-1, m-1) 좌상단으로부터 n x n 크기) 값이 전부 1이 되는지를 비교한다. (두세번째 for문) lockk을 복사해서 만든 tempLock에다가 연산한다. lockk 값은 변하면 안되므로. 그 이후 가운데가 모두 1이 되는지를 검사한다. 모두 1이 된다면 자물쇠에 맞는 열쇠라는 뜻이므로 true 리턴 후 끝내면 된다. 가운데가 모두 1이 되지 않는다면 key의 다음 이동 !
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기