99클럽 코테 스터디 14일차 TIL C++ 비트마스크, 브루트 포스

오늘의 학습 키워드

문제1 : 비트마스크, 브루트 포스

이번 문제에서는 주어진 행렬을 특정 조건에 맞게 변형하여 목표 상태에 도달하는 방법을 학습했습니다. 목표 상태와 현재 상태가 주어졌을 때, 최소 횟수로 행과 열을 뒤집어 목표 상태로 만들 수 있는지를 확인하는 문제입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/131703#qna

공부한 내용 본인의 언어로 정리하기

문제1 : 비트마스크, 브루트 포스

 

(1) BFS

처음에는 BFS(너비 우선 탐색) 을 사용해 목표 상태와 현재 상태를 비교하며 다른 열과 행을 찾아서, 그 열이나 행을 뒤집는 방식으로 접근했습니다. 그러나 이 방법은 계산량이 많아져 시간 초과가 발생했습니다. 특히 행렬의 상태가 복잡할수록 더 효율적인 접근이 필요함을 느꼈습니다.

 

(2) 아이디어

이 문제를 해결하기 위해 좋은 아이디어가 생각나지 않아서, 문제의 질문에 적힌 내용을 참고했습니다. 비트마스크와 브루트 포스를 결합하는 방법을 사용했습니다. 비트마스크를 활용해 각 가로와 세로의 반전 여부를 설정하고, 가능한 모든 조합을 통해 목표 상태에 도달할 수 있는지를 확인하는 방식입니다.

• 가로와 세로의 반전 순서는 상관없다: 목표 형태가 주어졌으므로 가로 또는 세로의 뒤집기만으로 목표 형태에 도달할 수 있는지 확인할 수 있습니다.
• 모든 경우의 수 미리 준비해두기: 가로와 세로 반전 여부에 대해 가능한 모든 조합을 제작한 후, 해당 조합으로 행렬을 뒤집어 목표 상태가 되는지 검사합니다.

(3) 비트연산

 

<< (왼쪽 시프트 연산자)

• x << n은 x의 비트를 왼쪽으로 n번 이동시킵니다.
• 왼쪽으로 이동하면 오른쪽에 빈 공간이 생기고, 그 공간은 0으로 채워집니다.
• 각 이동마다 값은 2배씩 증가하는 효과가 있습니다.

int x = 3;        // 3은 이진수로 00000011
int result = x << 2;  // 왼쪽으로 2번 이동하면 00001100
// result는 12 (10진수)입니다.

 

>> (오른쪽 시프트 연산자) 

• x >> n은 x의 비트를 오른쪽으로 n번 이동시킵니다.
• 오른쪽으로 이동하면 왼쪽에 빈 공간이 생기고, 그 공간은 일반적으로 0으로 채워집니다.
• 각 이동마다 값은 절반씩 줄어드는 효과가 있습니다.

int x = 12;       // 12는 이진수로 00001100
int result = x >> 2;  // 오른쪽으로 2번 이동하면 00000011
// result는 3 (10진수)입니다.

 

(4) 전체 풀이

이제 문제를 해결하기 위한 코드를 작성하겠습니다. 우선, 주어진 행렬의 특정 행이나 열을 반전시키는 함수를 정의하고, 비트마스크를 통해 가능한 모든 조합을 적용하는 방식으로 목표 상태를 확인하는 코드를 구현했습니다.

#include <vector>
#include <iostream>
#include <map>

using namespace std;

// 반전 함수 (가로 및 세로)
void reverse(vector<vector<int>>& vecT, int index, bool isRow) {
    int size = isRow ? vecT[0].size() : vecT.size();
    for (int i = 0; i < size; i++) {
        if (isRow) {
            vecT[index][i] = !vecT[index][i]; // 가로 반전
        } else {
            vecT[i][index] = !vecT[i][index]; // 세로 반전
        }
    }
}

// 비트에서 1의 개수를 세는 함수
int count_bits(int n) {
    int count = 0;
    while (n) {
        count += n & 1; // 마지막 비트가 1인지 확인
        n >>= 1;        // 비트를 오른쪽으로 이동
    }
    return count;
}

// 비트마스크를 사용한 가로/세로 반전 여부를 체크하는 함수
int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
    int h = beginning.size();
    int w = beginning[0].size();

    // 목표 상태와 초기 상태가 같으면 0번 뒤집기만으로 목표 상태가 되므로 바로 리턴
    if (beginning == target) return 0;

    // 모든 가로 반전 여부 조합 구하기
    map<int, vector<pair<int, int>>> vecMask;
    for (int row_mask = 0; row_mask < (1 << h); ++row_mask) {
        for (int col_mask = 0; col_mask < (1 << w); ++col_mask) {

            int cnt_bits = count_bits(row_mask) + count_bits(col_mask);
            pair<int, int> pairMask = {row_mask, col_mask};
            vecMask[cnt_bits].push_back(pairMask);
        }
    }

    // 가로에 대한 2진수 비트마스크 (모든 가로 반전 여부 조합을 시도)
    for (int i=0;i<=20;i++){
        for (pair<int, int> iter : vecMask[i]){
            vector<vector<int>> modified_board = beginning;
            int row_mask = iter.first;
            int col_mask = iter.second;

            // reverse V
            for (int i = 0; i < h; ++i) {
                if (row_mask & (1 << i)) {  // 해당 행을 반전
                    reverse(modified_board, i, true);
                }
            }

            // reverse H
            for (int j = 0; j < w; ++j) {
                if (col_mask & (1 << j)) {  // 해당 열을 반전
                    reverse(modified_board, j, false);
                }
            }

            // check result
            if (modified_board == target) return i;
        }
    }

    return -1;
}

오늘의 회고

이번 문제는 비트마스크와 브루트 포스의 조합을 통해 해결할 수 있었습니다. 처음에는 BFS로 접근했지만 시간 초과 문제를 해결하기 어려웠습니다. 이번 학습을 통해 다양한 접근 방법을 고민해보고, 비트마스크와 브루트 포스의 장단점을 이해하는 경험이 되었습니다.