백준(BOJ) Bitmask 기차가 어둠을 헤치고 은하수를 (15787) - Silver2

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

15787번: 기차가 어둠을 헤치고 은하수를

문제

N개의 기차가 어둠을 헤치고 은하수를 건너려고 한다.

기차는 20개의 일렬로 된 좌석이 있고, 한 개의 좌석에는 한 명의 사람이 탈 수 있다. 

기차의 번호를 1번부터 N번으로 매길 때, 어떠한 기차에 대하여 M개의 명령이 주어진다.

명령의 종류는 4가지로 다음과 같다.

• 1 i x : i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 태워라. 이미 사람이 타있다면 , 아무런 행동을 하지 않는다.
• 2 i x : i번째 기차에 x번째 좌석에 앉은 사람은 하차한다. 만약 아무도 그자리에 앉아있지 않았다면, 아무런 행동을 하지 않는다.
• 3 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 뒤로간다. k번째 앉은 사람은 k+1번째로 이동하여 앉는다. 만약 20번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.
• 4 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 앞으로간다. k번째 앉은 사람은 k-1 번째 자리로 이동하여 앉는다. 만약 1번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.

M번의 명령 후에 1번째 기차부터 순서대로 한 기차씩 은하수를 건너는데 조건이 있다.

기차는 순서대로 지나가며 기차가 지나갈 때 승객이 앉은 상태를 목록에 기록하며 이미 목록에 존재하는 기록이라면 해당 기차는 은하수를 건널 수 없다.

예를 들면, 다음 그림을 예로 들었을 때, 1번째 기차와 같이 승객이 앉은 상태는 기록되지 않았기 때문에 은하수를 건널 수있다. 2번째 기차와 같은 상태도 기록되지 않았기 때문에 2번째 기차도 은하수를 건널 수 있다. 3번째 기차는 1번째 기차와 승객이 앉은 상태가 같으므로 은하수를 건널 수 없다.

처음에 주어지는 기차에는 아무도 사람이 타지 않는다.

은하수를 건널 수 있는 기차의 수를 출력하시오.

입력

입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. 

 

문제 해결

해당 문제는 승객이 있거나 없거나 0 또는 1로 표현이 가능하다 이를 통해 비트 마스크 연산을 이용하면 시간초과에 빠지지 않고 빠르게 해결이 가능하다. c++의 경우 비트마스크 연산을 도와주는 bitset 라이브러리가 있어서 이를 사용하면 조금 더 쉽게 코드를 구현할 수 있다.

 

기본적인 Bitset 사용법은 아래와 같다.

https://learn.microsoft.com/ko-kr/cpp/standard-library/bitset-class?view=msvc-170 

bitset 클래스

all	이 bitset 의 모든 비트를 테스트하여 모두 로 설정되어 true있는지 여부를 확인합니다.
any	멤버 함수는 시퀀스의 모든 비트가 1로 설정되었는지 여부를 테스트합니다.
count	멤버 함수는 비트 시퀀스에 설정된 비트 수를 반환합니다.
flip	bitset에 있는 모든 비트의 값을 반전하거나 지정된 위치에서 단일 비트를 반전합니다.
none	bitset 개체에서 1로 설정된 비트가 없는지 테스트합니다.
reset	bitset에 있는 모든 비트를 0으로 재설정하거나 지정된 위치의 비트를 0으로 재설정합니다.
set	bitset에 있는 모든 비트를 1로 설정하거나 지정된 위치의 비트를 1로 설정합니다.
size	bitset 개체의 비트 수를 반환합니다.
test	bitset에서 지정된 위치의 비트가 1로 설정되어 있는지 테스트합니다.
to_string	bitset 개체를 문자열 표현으로 변환합니다.
to_ullong	bitset에 있는 비트 값의 합을 unsigned long long로 반환합니다.
to_ulong	bitset 개체를 bitset을 초기화하는 데 사용되는 경우 포함된 비트 시퀀스를 생성할 unsigned long로 변환합니다.

이번 문제는 해당 명령어 중 to_string만 사용하였다. 

일단 문제와 같이 총 4개의 명령어를 switch case 문을 통해 처리 했다. 

• 1번 케이스의 경우 주어진 좌석에 승객이 있던 없던 1로 만들어준다.
• 2번 케이스의 경우 주어진 좌석에 승객이 있던 없던 0으로 만들어준다.
• 3번 케이스의 경우 주어진 열차에 있는 모든 승객들을 왼쪽으로 한 칸씩 옮겨준다.
• 4번 케이스의 경우 주어진 열차에 있는 모든 승객들을 오른쪽으로 한 칸씩 옮겨준다.

switch (first)
        {
        case 1:
            cin >> second >> third;
            bits[second-1][third-1] = 1; 
            break;
        case 2:
            cin >> second >> third;
            bits[second-1][third-1] = 0; 
            break;
        case 3:
            cin >> second;
            bits[second-1] <<= 1;
            break;
        case 4:
            cin >> second;
            bits[second-1] >>= 1;
            break;
        }

처음 vector를 이용하여 하나씩 처리하는 방식으로 했을 때는 상당히 오래걸렸는데 비트 연산을 사용하니 몇줄 안되는 코드로 명령문 처리가 끝났다... 이제 가장 중요한 중복처리를 해야하는데 여기서 또 한번 비트연산의 힘이 나온다. 일단 중복값을 허용하지 않는 자료구조인 set을 사용하였다. set은 기본적으로 key value값으로 중복값을 허용하지 않아 중복처리를 할 때 빠르게 처리가 가능하다. 우선 현재는 각각의 열차들이 비트로 표현되어 있기 때문에 이를 모두 string자료형으로 한 번 바꿔주었다. 이렇게 하면 모든 열차들에 대한 정보들이 바로 string 형태로 저장되고 이 string을 key로 set 자료구조에 넣으면 간단하게 해결이 가능하다.

set<string>unique_bits;

    for(ll i=0; i<n; i++){
        unique_bits.insert(bits[i].to_string());
    }

    cout << unique_bits.size()  << "\n";

코드만 보면 간단하지만 이 문제를 푸는데 엄청난 시간이 걸렸다. 일단 비트연산자가 익숙하지 않아 많은 시행착오를 겪었다. 자주 사용하는 패턴은 아니지만 반드시 알아야 하는 알고리즘이다.

 

전체 코드

#include <iostream>
#include <bitset>
#include <string>
#include <set>

#define MAX_SIZE 100000
using namespace std;

typedef long long ll;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r" ,stdin);

    ll n = 0; // 기차의 수
    ll m = 0; // 명령의 수
    cin >> n >> m;

    bitset<20>bits[MAX_SIZE];

    ll first, second, third;
    for(ll i=0; i<m; i++){
        cin >> first;
        switch (first)
        {
        case 1:
            cin >> second >> third;
            bits[second-1][third-1] = 1; 
            break;
        case 2:
            cin >> second >> third;
            bits[second-1][third-1] = 0; 
            break;
        case 3:
            cin >> second;
            bits[second-1] <<= 1;
            break;
        case 4:
            cin >> second;
            bits[second-1] >>= 1;
            break;
        }
    }

    set<string>unique_bits;

    for(ll i=0; i<n; i++){
        unique_bits.insert(bits[i].to_string());
    }

    cout << unique_bits.size()  << "\n";
    
    
    return 0;
}

수 많은 시도 끝에 겨우 성공..