[알고리즘 중급] 비트마스크

💚 14225 부분수열의 합

- S의 부분 수열의 개수는 2^N가지

- N <= 20이기 때문에, 부분 수열을 모두 만들어본다.

- 부분 수열을 만드는 방법

1) 재귀 호출

2) 비트마스크

#include <iostream>
using namespace std;
// c[i]: 수 i를 만들 수 있음
// 최대 20 * 10만까지 가능하기 때문에 그 바로 다음 숫자까지 접근 가능해야 한다.
bool c[20 * 100000 + 2];
int a[20];
int n;

int main() {
    cin >> n;
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }

    // 비트마스크로 모든 부분 수열 조합을 만든다.
    for(int i = 0;i < (1 << n);i++) {
        int sum = 0;
        for(int j = 0;j < n;j++) {
            if(i & (1 << j)) {
                sum += a[j];
            }
        }
        c[sum] = true;
    }

    for(int i = 1;;i++) {
        if(c[i] == false) {
            cout << i << '\n';
            break;
        }
    }

    return 0;
}

💚 1062 가르침

- N개의 단어가 주어졌을 때

- K개의 글자로만 이루어진 단어의 개수를 고르는 문제

- 모든 단어는 anta로 시작하고

- 모든 단어는 tica로 끝난다.

- N <= 50, 단어의 길이 <= 15

- 먼저 a,n,t,i,c는 가르쳐야 한다.

- 즉 26 -5 개의 글자 중에서 K - 5개를 고르는 문제

 

각각의 단어에 대해서 모든 글자를 검사한다는 것은 너무 오래 걸린다. 👉 O(단어의 개수 * 각 단어의 길이)

이 부분을 O(단어의 개수)로 줄일 수 있다.

실제로 그 단어가 무엇인지가 중요한 것이 아니다.

그 단어에 알파벳이 어떤 순서로 이루어져 있는지가 중요한 것이 아니다.

각 단어에 속해있는 알파벳이 무엇인지만 중요하다

word[i] = i 번째 단어를 구성하고 있는 알파벳을 비트마스크

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;
// index: 알파벳 인덱스
// mask: 배운 알파벳의 비트마스크

int count(int mask, vector<int>  &words) {
    int cnt = 0;
    for(int word : words) {
        // (1 << 26) - 1 - mask 로 미포함된 알파벳만 남기기
        // 비트마스크의 결과가 1이 아니면 word의 알파벳 중 mask에 포함되지 않은 알파벳이 있다는 뜻이다.
        if((word & (1 << 26) - 1 - mask) == 0) {
            cnt += 1;
        }
    }
    return cnt;
}

bool basic_alphabets(int index) {
    return index == 'a' - 'a' || index == 'n' - 'a' || index == 't' - 'a' || index == 'i' - 'a' || index == 'c' - 'a';
}

int go(int index, int k, int mask, vector<int> &words) {
    if(k < 0) return 0;

    // 마지막 탐색
    if(index == 26) {
        return count(mask, words);
    }

    int ans = 0;
    // index번째 알파벳을 배우는 경우
    int t1 = go(index + 1, k - 1, mask | (1 << index), words);
    if(ans < t1) ans = t1;
    // index번째 알파벳을 배우지 않는 경우
    // 이 때는 a, n, t, i, c에는 해당되지 않아야 함
    if(!basic_alphabets(index)) {
        int t2 = go(index + 1, k, mask, words);
        if(ans < t2) ans = t2;
    }

    return ans;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> words(n);
    for(int i = 0;i < n;i++) {
        string s;
        cin >> s;
        for(char c : s) {
            words[i] |= (1 << (c - 'a'));
        }
    }
    cout << go(0, k, 0, words) << '\n';
    return 0;
}

💚 13460 구슬 탈출2

- 보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 문제

- 만약 10번 이내에 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력

- 같은 방향으로 연속해서 두 번 이상 이동하는 건 의미가 없다.

- 한 방향으로 이동한 다음 반대 방향으로 바로 이동하는 것도 의미가 없다.

- 가능한 이동방법의 수: 4 * 2^9 = 2,048 가지

 

- 먼저, 이동 가능한 방법을 비트마스크를 이용해서 4^10 가지를 만든 다음

- 앞 페이지에 나온 두 가지 경우를 모두 제외시킨다.

- 4^10을 만들기 위해 0부터 2^20까지의 수를 모두 만들고

- 4진법으로 변환해서 경우의 수를 모두 만든다.

- 동시에 두 개의 공을 이동시키는 것은 어렵기 때문에 공을 하나씩 움직여서 두 공이 움직이지 않을 때까지 이동

📌 비트 마스크 풀이법

#include <iostream>
#include <vector>
using namespace std;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

// 10번 제한
const int LIMIT = 10;
// k = 길이가 10인 4진법 수
vector<int> gen(int k) {
    vector<int> a(LIMIT);
    for(int i = 0;i < LIMIT;i++) {
        a[i] = (k & 3);
        k >>= 2;
    }
    return a;
}

bool valid(vector<int> &dir) {
    int l = dir.size();
    for(int i = 0;i < l - 1;i++) {
        // 반대 방향으로 바로 이동하는 건 안됨
        if(dir[i] == 0 && dir[i + 1] == 1) return false;
        if(dir[i] == 2 && dir[i + 1] == 3) return false;
        if(dir[i] == 3 && dir[i + 1] == 2) return false;
        if(dir[i] == 1 && dir[i + 1] == 0) return false;
        // 연속으로 같은 방향으로 이동하는 것도 안됨
        if(dir[i] == dir[i + 1]) return false;
    }
    return true;
}

// 이동 여부, 구멍통과 여부
pair<bool, bool> simulate(vector<string> &a, int k, int &x, int &y) {
    // 구슬의 위치가 빈칸이면 종료
    // 두 구슬 중 하나가 통과되어도 계속 진행
    if (a[x][y] == '.') return make_pair(false, false);

    bool moved = false;
    while(true) {
        int nx = x + dx[k];
        int ny = y + dy[k];

        if(a[nx][ny] == '#') {
            return make_pair(moved, false);
        }
        else if(a[nx][ny] == 'R' || a[nx][ny] == 'B') {
            return make_pair(moved, false);
        }
        else if(a[nx][ny] == '.') {
            swap(a[nx][ny], a[x][y]);
            x = nx;
            y = ny;
            moved = true;
        }
        else if(a[nx][ny] == 'O') {
            // 더 이상 구슬은 없기 때문에 빈칸으로 대체
            a[x][y] = '.';
            moved = true;
            return make_pair(moved, true);
        }
    }

    // 절대로 호출될 일이 없는 구문
    return make_pair(false, false);
}
// dir 벡터에 따라 구슬 이동
int check(vector<string> a, vector<int> &dir) {
    int n = a.size();
    int m = a[0].size();
    int rx, ry, bx, by;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            if(a[i][j] == 'R') {
                rx = i; ry = j;
            }

            else if(a[i][j] == 'B') {
                bx = i; by = j;
            }
        }
    }

    int cnt = 0;
    for(int k : dir) {
        cnt += 1;
        bool hole1 = false, hole2 = false;
        while(true) {
            auto red = simulate(a, k, rx, ry);
            auto blue = simulate(a, k, bx, by);

            // 이동 종료
            if(red.first == false && blue.first == false) {
                break;
            }
            if(red.second) hole1 = true;
            if(blue.second) hole2 = true;
        }

        if(hole2) return -1;
        if(hole1) return cnt;
    }
    return -1;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }
    int ans = -1;
    for(int k = 0;k < (1 << (LIMIT * 2));k++) {
        vector<int> dir = gen(k);
        if(!valid(dir)) continue;
        int cur = check(a, dir);
        if(cur == -1) continue;
        if(ans == -1 || ans > cur) ans = cur;
    }
    cout << ans << '\n';
    return 0;
}

📌 DFS를 이용한 풀이법

#include <iostream>
#include <cstring>
#include <set>
#include <tuple>
using namespace std;
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
char board[10][10];
// 빨간 구슬과 파란 구슬의 방문 전적 확인
set<tuple<int,int,int,int>> visited;
// DFS
void go(int rr, int rc, int br, int bc, int cnt);
int answer = 11;
int n, m;
int goal_r, goal_c;
int main(void){
    // red_row, red_column, blue_row, blue_column,
    int rr, rc, br, bc;
    cin >> n >> m;
    for(int i = 0;i < n;i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
            // R, B, O는 특수한 값이므로 별도 변수에 저장
            // 최대한 간편한 계산을 위해 board에는 #, .만 저장
            if(board[i][j] == 'R'){
                rr = i;
                rc = j;
                board[i][j] = '.';
            }
            else if(board[i][j] == 'B'){
                br = i;
                bc = j;
                board[i][j] = '.';
            }
            else if(board[i][j] == 'O'){
                goal_r = i;
                goal_c = j;
                board[i][j] = '.';
            }
        }
    }
    visited.insert({rr, rc, br, bc});
    go(rr, rc, br, bc, 0);
    if(answer > 10) {
        cout << -1;
    }
    else {
        cout << answer;
    }
}
/*
 * 최대한 간편하게 풀기 위해 #, .만 구성
 * 중간에 충돌하는 경우 배제하고 벽까지 이동해버리고, 경로 표기
 * 이동이 끝난 뒤 표기된 경로를 참고해서 이동 중간에 충돌하는 경우와 구멍에 빠지는 경우 처리
 */
void go(int rr, int rc, int br, int bc, int cnt){
    // 단계별로 빨간 구슬과 파란 구슬의 위치를 파악하기 위함
    int route_r[10][10];
    int route_b[10][10];
    // 나올 수 있는 최소 이동값
    if(answer == 1) return;
    // answer 이상 넘어가면 더 탐색할 필요가 없음
    if(cnt >= answer) return;
    // 빨간 구슬의 통과 여부를 떠나서 파란구슬이 통과되면 실패
    if(br == goal_r && bc == goal_c) return;
    // 파란 구슬은 통과하지 않았고(위에서 return되지 않음으로 전제) 빨간 구슬만 통과하고 최소횟수 갱신
    if((rr == goal_r && rc == goal_c) && answer > cnt) {
        answer = cnt;
        return;
    }
    // 상하좌우로 벽까지 이동
    for(int dir = 0;dir < 4;dir++){
        memset(route_r, 0, sizeof(route_r));
        memset(route_b, 0, sizeof(route_b));
        int move_r = 0;
        int move_b = 0;
        int nrr = rr, nrc = rc, nbr = br, nbc = bc;
        // 벽까지 이동
        while(board[nrr][nrc] != '#'){
            route_r[nrr][nrc] = move_r++;
            nrr += dr[dir];
            nrc += dc[dir];
        }
        // 벽까지 이동해있으니 뒤로 한 걸음
        nrr -= dr[dir];
        nrc -= dc[dir];
        while(board[nbr][nbc]!= '#'){
            route_b[nbr][nbc] = move_b++;
            nbr += dr[dir];
            nbc += dc[dir];
        }
        nbr -= dr[dir];
        nbc -= dc[dir];
        // 두 구슬 모두 움직이지 않았을 때 고려하지 않는 케이스
        if(rr == nrr && rc == nrc && br == nbr && bc == nbc) {
            continue;
        }
        // 골을 지나가면(경로 중에 골 존재) 골처리
        if(route_r[goal_r][goal_c] > 0){
            nrr = goal_r;
            nrc = goal_c;
        }
        if(route_b[goal_r][goal_c] > 0){
            nbr = goal_r;
            nbc = goal_c;
        }
        // 충돌 2번째 케이스 - 골 들어가지 않는 이상 좌표가 동일하면 충돌임
        if(nrr == nbr && nrc == nbc && !(goal_r == nrr && goal_c == nrc)){
            // 파란 구슬이 먼저 도착했다.
            if(route_r[nrr][nrc] > route_b[nbr][nbc]){
                nrr -= dr[dir];
                nrc -= dc[dir];
            }
            // 빨간 구슬이 먼저 도착했다.
            else if(route_r[nrr][nrc] < route_b[nbr][nbc]){
                nbr -= dr[dir];
                nbc -= dc[dir];
            }
        }
        if(!visited.count({nrr, nrc,nbr, nbc})){
            visited.insert({nrr, nrc,nbr, nbc});
            go(nrr, nrc, nbr, nbc, cnt + 1);
            visited.erase({nrr, nrc,nbr, nbc});
        }
    }


}

 

💚 2048(Easy)

상하좌우로 최대 5번 ➡️ 4^5

위 문제와 다르게 연속적으로 같은 방향으로, 반대 방향으로 2번 이상 이동하는 것 의미 있음

 

2차원 배열에 first에는 해당 수를, second에는 합쳐진 여부를 저장한다.

여기서 중요한 점은 무언가를 한 방향으로 이동할 때는 해당 방향에 가까운 내용물부터 옮겨야한다는 점이다.

이는 [백준]2933: 미네랄문제에서도 주의했어야하는 점이다. 

[백준] 2933: 미네랄

 

그리고 코드가 길기 때문에 오타를 주의해야 한다.

#include <iostream>
#include <vector>
using namespace std;
const int LIMIT = 5;
int n;
vector<int> gen(int k) {
    vector<int> a(LIMIT);
    for(int i = 0;i < LIMIT;i++) {
        a[i] = (k & 3);
        k >>= 2;
    }

    return a;
}

int check(vector<vector<int>> &a, vector<int> &dirs) {
    // first에는 숫자, second에는 합쳐진 여부
    vector<vector<pair<int, bool>>> d(n, vector<pair<int, bool>> (n));

    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            d[i][j].first = a[i][j];
        }
    }

    // 0: down 1: up 2: left 3: right
    for(int dir: dirs) {
        bool ok = false;
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < n;j++) {
                d[i][j].second = false;
            }
        }


        while(true) {
            ok = false;
            if(dir == 0) {
                for(int  i = n - 2;i >= 0;i--) {
                    for(int j = 0;j < n;j++) {
                        // 수가 없으면 패스
                        if(d[i][j].first == 0) continue;
                        // 아래에 수가 없으므로 전달
                        if(d[i + 1][j].first == 0) {
                            d[i + 1][j].first = d[i][j].first;
                            d[i + 1][j].second = d[i][j].second;
                            d[i][j].first = 0;
                            ok = true;
                        }
                        else if(d[i + 1][j].first == d[i][j].first) {
                            // 모두 합쳐진 적 없어야 함
                            if(d[i][j].second == false && d[i + 1][j].second == false) {
                                d[i + 1][j].first *= 2;
                                d[i + 1][j].second = true;
                                d[i][j].first = 0;
                                ok = true;
                            }
                        }
                    }
                }
            }
            else if(dir == 1) {
                for(int i = 1;i < n;i++) {
                    for(int j = 0;j < n;j++) {
                        if(d[i][j].first == 0) continue;
                        if(d[i - 1][j].first == 0) {
                            d[i - 1][j].first = d[i][j].first;
                            d[i - 1][j].second = d[i][j].second;
                            d[i][j].first = 0;
                            ok = true;
                        }
                        else if(d[i - 1][j].first == d[i][j].first) {
                            if(d[i][j].second == false && d[i - 1][j].second == false) {
                                d[i - 1][j].first *= 2;
                                d[i - 1][j].second = true;
                                d[i][j].first = 0;
                                ok = true;
                            }
                        }
                    }
                }
            }
            else if(dir == 2) {
                for(int j = 1;j < n;j++) {
                    for(int i = 0;i < n;i++) {
                        if(d[i][j].first == 0) continue;
                        if(d[i][j - 1].first == 0) {
                            d[i][j - 1].first = d[i][j].first;
                            d[i][j - 1].second = d[i][j].second;
                            d[i][j].first = 0;
                            ok = true;
                        }
                        else if(d[i][j - 1].first == d[i][j].first) {
                            if(d[i][j - 1].second == false && d[i][j].second == false) {
                                d[i][j - 1].first *= 2;
                                d[i][j - 1].second = true;
                                d[i][j].first = 0;
                                ok = true;
                            }
                        }
                    }
                }
            }
            else if(dir == 3) {
                for(int j = n - 2;j >= 0;j--) {
                    for(int i = 0;i < n;i++) {
                        if(d[i][j].first == 0)  continue;
                        if(d[i][j + 1].first == 0) {
                            d[i][j + 1].first = d[i][j].first;
                            d[i][j + 1].second = d[i][j].second;
                            d[i][j].first = 0;
                            ok = true;
                        }
                        else if(d[i][j + 1].first == d[i][j].first){
                            if(d[i][j + 1].second == false && d[i][j].second == false) {
                                d[i][j + 1].first *= 2;
                                d[i][j + 1].second = true;
                                d[i][j].first = 0;
                                ok = true;
                            }
                        }
                    }
                }
            }
            // 이동이 없음
            if(ok == false) break;
        }
    }

    int ans = 0;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            if(ans < d[i][j].first) {
                ans = d[i][j].first;
            }
        }
    }

    return ans;
}
int main() {
    cin >> n;
    int ans = 0;
    vector<vector<int>> a(n, vector<int> (n));

    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            cin >> a[i][j];
        }
    }
    for(int k = 0;k < (1 << (LIMIT * 2));k++) {
        vector<int> dirs = gen(k);
        int cur = check(a, dirs);
        if(ans < cur) ans = cur;
    }

    cout << ans << '\n';
    return 0;
}