[C++] 백준 1236번: 성 지키기 (비트 마스크)

🔗 문제

https://www.acmicpc.net/problem/1236

 

 

✏️ 풀이

풀이는 간단하다.

각 행과 열에서 X 경비원이 없는 곳의 개수를 세면 된다.

그리고 그 개수 중 큰 것이 답이 된다.

 

 

예제 2를 보자. 정답은 3이다.

• 행에서는 X가 없는 곳이 3 줄
• 열에서는 X가 없는 곳이 1 줄

5 8
....XXXX
........
XX.X.XX.
........
........

 

배열로 확인하면 되지만 비트마스킹으로 푼 것에 의의를 두었다.

안 쓰면 까먹게 되는 지식들.. 다시 한 번 정리하며 풀이 소스를 올린다.

 

비트 설정 (set)

int number = 0b0000; // 초기 값
int mask = 0b0001;   // 1을 설정할 마스크

number |= mask;      // number는 이제 0001

 

비트 해제 (unset)

int number = 0b0001; // 초기 값
int mask = 0b1110;   // 0을 설정할 마스크

number &= mask;      // number는 이제 0000

 

비트 확인 (check)

int number = 0b0001; // 초기 값
int mask = 0b0001;   // 체크할 비트 마스크

boolean isSet = (number & mask) != 0; // isSet은 true

 

비트 토글

int number = 0b0001; // 초기 값
int mask = 0b0001;   // 1을 토글할 마스크

number ^= mask;      // number는 이제 0000
number ^= mask;      // 다시 0001

 

⚠️ 주의할 점

N과 M은 50보다 작거나 같은 자연수이다.

 

int는 32비트이기 때문에 long long 64비트를 이용해야 한다. 

 

 

💾  소스

#include <iostream>

using namespace std;

int main() 
{
    char ch;
    int N, M;
    
    long long row = 0, col = 0;
    
    cin >> N >> M;
    
    int r = N, c = M;
    for (int i=0; i<N; ++i)
    {
        for (int j=0; j<M; ++j)
        {
            cin >> ch;
        
            if (ch != 'X') continue;
            
            if((row & (1LL << i)) == 0)
            {
                // row에서 i행이 체크되지 않았다면 체크한다.
                row |= (1LL << i);
                --r;
            }
            
            if ((col & (1LL << j)) == 0)
            {
                // col에서 j행이 체크되지 않았다면 체크한다.
                col |= (1LL << j); 
                --c;
            }
        }
    }

    cout << (r > c ? r : c);

    return 0;
}