[C++로 풀이] 자물쇠와 열쇠 (완전 탐색)⭐⭐⭐

Date:     Updated:

카테고리:

태그:

📌 자물쇠와 열쇠

난이도 ⭐⭐⭐

🚀 문제

image

image


🚀 내 풀이 ⭕

✈ 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 모두 종료.

원래 이와 같은 로직으로 짜는게 내 계획이었다. 근데 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;
    }
}

image

현재의 모습에서 시계방향으로 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`과 일치해질 때를 찾는다.

image

  • 전체 크기 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 번만 이동해보아도 keylock을 열 수 있는지 없는지를 판단할 수 있다. (key의 좌상단이 될 수 있는 경우가 25번이다.) key 4가지 회전별로 한번씩 살펴보므로 총! 최대 이동 횟수는 4 * 25 = 100 번 밖에 되지 않는다. 이 최대 비교 횟수 동안 한번도 lock과 일치하지 않았다면 결과는 false가 되는 것이다.

이 문제의 mn의 최대 크기는 각각 20이기 때문에 lockk의 최대 크기는 58 x 58 = 3364 가 된다. 그리고 총 비교 횟수는 4 x 39 x 39 = 6084 번 밖에 되지 않는다.

image

위 예제의 경우 key가 90도로 회전한 모습에서 19번 이동 했을 때 위와 같이 lock과 일치하는 것을 찾을 수 있다. (lockk 의 가운데 n x n 크기가 전부 1이 되야 함! 2나 0인게 하나라도 있으면 안된다.)

  • lock의 원소가 2가 된다는 것은 -> key의 돌기와 lock의 돌기가 만났다는 것 (이러면 안됨. 돌기와 홈끼리만 맞아야함!)
  • lock의 원소가 0이라는 것은 -> key도 홈이여서 lock의 홈이 채워지지 않았다는 것.

따라서 lock의 원소가 모~두 1이 될 때, 그 keylock을 열 수 있는 것이다.

image

만약 key의 크기가 2라면 이런 모습이 될 것이고 (keylockk안에서 이동을 총 16번 할 수 있겠다.)

image

key의 크기가 1이라면 이런 모습이 될 것이다. keylock 안에서만 움직이면 되서 lockklock과 동일한 크기일 것이다. 이 경우 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 배치
    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));

bumpPoskey의 돌기 위치 저장

    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문) keylockk 내에서 이동할 수 있는 (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의 다음 이동 !



🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기

댓글 남기기