정답논리

9달전에 못풀어서 DFS방식의 정답을 보고 푼 기억이 있는데, DFS방식도 모르겠고 이번 비트마스크방식으로도 이해를 하지못해 다시 한번 비트마스크 형식의 답을 보고 푼 기억이 있다. 정답을 봐도 참 복잡했던 문제였다.

비트마스크로 풀 논리를 기반으로 문제를 차근차근 분해해보자

상,하,좌,우 4방향으로 움직일 수가 있고 10번 이내로 구슬을 굴려야하고 그 이상 굴리면 -1 처리한다.

적어도 내가 이해한 바로는 먼저 비트마스크는 경우의 수를 찾는데 유용하게 사용됬다.
각 한 케이스 ,한 점 또는 한 사건에 대하여 n개의 선택지가 있을때 모든 경우의 수는 n^k이다 ( n: 선택지, k: 사건의 수)

이 문제의 경우 한 좌표 (x, y)에 대하여 움직일 수 있는 방향이 4가지이다. 그리고 최대 10번 움직일수가 있다.
즉 선택지의 경우는 4이고 사건의 수는 10이 되므로 이 문제에서 고려할 수 있는 경우의 수는 4^10개이다.
bitmask = 0 ~ (1<<4^10 ,2^20)이다.

경우의 수를 조금 더 줄여보자.

이 문제에 한해서만 경우의 수를 조금 줄일 수 있다.

1. 왼쪽으로 굴렸다가 다시 오른쪽으로 굴린경우 또는 그 반대의 경우

이럴빠에 그냥 오른쪽으로만 굴린 경우를 생각하면 되므로 이 경우는 의미가 없다.

2. 한 방향으로 2번 굴리는 경우

한방향으로 끝까지 굴렸다가 다음에 같은 방향으로 또 굴리면 어짜피 구슬은 이동하지 않기 때문에 의미가 없다.
1, 2의 코드는 아래와 같다.

먼저 모든 경우의 수를 비트마스크로 표현한다.

for(int k=0; k<(1<<(LIMIT*2)); ++k){
        
        vector<int> aCase = generateAcase(k);
        if(!validationCase(aCase)) continue;
        
        int cur = check(map, aCase);
        if(cur == -1) continue;
        if(ans == -1 || ans > cur) ans = cur;
    }

각 경우의 수에 대해서 10번을 어떻게 굴릴지 미리 정한다.

vector<int> generateAcase(int k)
{
   vector<int> aCase(LIMIT);
   for(int i=0; i<LIMIT; ++i){
       aCase[i] = (k & 3);
       k = k >> 2;
   }
   
   return aCase;
}

이런 아이디어가 있다는것에 놀라웠다.
우선 파라미터 k는 단순한 정수이지만 우리는 이것을 정수를 쓰는게 아니라 이 정수가 가진 비트를 이용하는 것이다. 그러므로 이 정수가 어떤 정수를 표현하던 그것은 중요한것이 아니다. 중요한것은 32비트 0,1이다.

정수 k는 0000001010010101001011…..111의 32비트다. 우리는 여기서 하위 10비트에만 신경을 쓸것이다. 총 이동 기울일 수 있는 수가 10회이고 그 이상은 -1 처리하기 때문이다.

3을 32비트 이진수로 나타내면 0000….0011이다. 3과 비트 k를 and 연산을 하면 나올 수 있는 경우의 수가

000…000 > 0
000…001 > 1
000…010 > 2
000…011 > 3
이므로 어떠한 비트 k와 연산하여도 저 경우의 수를 구할 수 있다. 저 4가지의 경우는 각 상,하,좌,우 이동 할 수 있는 경우의 수 4가지를 뜻한다.
그리고 우측으로 2번 시프트 연산을 함으로써 k째 경우의 수의 첫번째 이동경로(인덱스 0)가 끝나고 두번째 이동 경로를 결정한다 ( 인덱스 1) 이런식으로 10번 loop를 돌면서 ( 총 이동횟수 10회 가능) 한번의 사건 k에 대하여 이동가능한 경우 10가지를 모두 알아본다.

bool validationCase(const vector<int> aCase)
{
    for(int i=0; i+1<aCase.size(); ++i){
        
        if(aCase[i] == 0 && aCase[i+1]==1) return false;
        if(aCase[i] == 1 && aCase[i+1]==0) return false;
        if(aCase[i] == 2 && aCase[i+1]==3) return false;
        if(aCase[i] == 3 && aCase[i+1]==2) return false;
        if(aCase[i] == aCase[i+1]) return false;
    }
    return true;
}

위 코드는 의미없는 경우의 수를 줄인다.

int check(vector<string> map, vector<int>& dir)
{
    int n = map.size();
    int m = map[0].size();
    
    int hx,hy,rx,ry,bx,by;
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            if(map[i][j] == 'O'){
                hy = i; hx = j;
            }
            else if(map[i][j] == 'R'){
                ry = i; rx = j;
            }
            else if(map[i][j] == 'B'){
                by = i; bx = j;
            }
        }
    }
    
    int cnt = 0;
    for(int k : dir){
        
        cnt += 1;
        bool redHole = false,blueHole = false;
        
        while(true){
            
            auto red = move(map,k,rx,ry);
            auto blue = move(map,k,bx,by);
            
            if(red.first == false && blue.first == false) break;
            
            if(red.second) redHole = true;
            if(blue.second) blueHole = true;
        }
        
        if(blueHole) return -1;
        if(redHole) return cnt;
    }
    return -1;
}

경우의 수 k로 이미 10회의 이동경로가 만들어진 dir와 map을 파라미터로 받는다.
각 구멍,빨간구슬,파란구슬의 좌표를 찾아 변수에 초기화 한다.

그 후 dir에 미리 초기화된 방향으로 구슬들을 이동 시킨다.

에러처리는 다음과 같다.

구슬이 둘다 움직이지 않은 경우 -> 다음 방향으로 이동
각 구슬들이 구멍에 빠진 경우 -> 각 구슬들에 해당하는 플래그를 true로 설정
파란구슬이 빠졌다면 ( 파란구슬 하나 && 파란구슬 and 빨간구슬) 무조건 -1 처리
앞서 파란 구슬이 빠진 모든 경우에 대해서는 -1 처리를 했으므로
이 경우는 빨간 구슬 하나만 빠진 경우이므로 cnt를 return
그 외의 경우는 모두 -1

int cur = check(map, aCase);
        if(cur == -1) continue;
        if(ans == -1 || ans > cur) ans = cur;

cur은 -1 또는 cnt의 값을 같게 되는데 -1 이면 구슬이 잘못된 경우이므로 다른 경우의 수 시작
cnt일 경우 ans보다 작으면 ans에 대입함으로서 ans 업데이트

pair<bool, bool> move(vector<string> &map,int k,int &x,int &y)
{
    if(map[y][x] == '.') return make_pair(false, false);
    
    int n = map.size();
    int m = map[0].size();
    
    bool moved = false;
    
    while (true) {
        int ny = y + dy[k];
        int nx = x + dx[k];
        
        if(map[ny][nx] == '#') return make_pair(moved, false);
        else if(map[ny][nx] == 'R' || map[ny][nx] == 'B' ) return make_pair(moved, false);
        else if(map[ny][nx] == '.'){
            moved = true;
            swap(map[y][x], map[ny][nx]);
            y = ny;
            x = nx;
        }
        else if(map[ny][nx] == 'O'){
            map[y][x] = '.';
            moved = true;
            return make_pair(moved, true);
        }
    }
    
    return make_pair(false, false);
}

구슬이 굴러감에 따라 구슬의 위치가 바뀌므로 ‘ . ‘와 ‘R’ 또는 ‘B’를 스왑한다. 그래서 call by reference로 파라미터 map을 전달받는다.

맨처음 if(map[y][x] == ‘.’) return make_pair(false, false);는 어떤 구슬이 이미 구멍에 빠진 경우이므로 에러처리를 한다.

그리고 방향 k에 대해 끝까지 굴려야 하니까 while문 안에서 계속 방향 k를 원래 좌표에 더한다.
그리고 각각의 에러에 대해 , 움직였는지 또는 구멍에 빠졌는지 pair로 return 한다.

벽(#)에 닿을 경우 더 이상 움직지 않는 경우 (움직이지 않음, 구멍에 빠지지 않음)을 리턴한다.
이 경우 check 함수 내에서 if(red.first == false && blue.first == false) break;을 통해
둘다 벽에 부딫혔을 경우 다음 방향으로 전환하기 위함이다.
‘ . ‘ 인 경우, 움직였음(moved)를 true로 표시하고
구슬과 점의 좌표를 스왑함으로써 움직였단것을 map에 기록한다.
구슬의 좌표는 새 좌표로 바꾼다.
구멍에 빠진 경우
구슬은 구멍에 빠졌음으로 구슬을 점으로 바꾸고 (움직였음, 구멍에 빠졌음)을 리턴한다.
check 함수에서
if(red.second) redHole = true;
if(blue.second) blueHole = true;
로 각 구슬들이 구멍에 들어갔는지 안들어갔는지 확인하고 스코프의 밖에서

if(blueHole) return -1;
if(redHole) return cnt;
파란구슬이 나갔는지 빨간 구슬이 나갔는지에 따라 정답과 -1처리를 하기 위해 사용된다.

그리고 check 함수와 move 함수에서 왜 각각 while(true)를 사용할까 고민을 해보았다.

우선 move함수에서 while문은 바로 이해가 갔다. 구슬을 ‘중력에 의해 굴리는 것’이므로 #이던 0이던 또는 다른 구슬에 막혀 굴러가지 못할때까지 굴려야하기 때문이다.

그렇다면 check 함수에서는 왜 while문을 썼을까?
파란구슬과 빨간구슬의 순서때문이다.

while(true){
            
// 코드상으로는 빨간 구슬을 먼저 굴리고 파란 구슬을 굴린다.
// 구슬이 RB 순서로 정렬해있을 경우에는 문제가 없다.
// 그러나 BR 순서로 정렬해있을 경우에는 빨간 구슬을 먼저 굴리는데 파란구슬에 막혀 (움직이지 않음, 구멍에 빠지지 않음)
// 을 리턴한다.
// 그래서 어떤 순서에 의해 구슬을 굴리지 못하는 경우가 발생하지 않도록 무한 루프를 이용하여
// 다음 방향으로 전환을 해야할때에만 루프를 빠져나올 수 있게 한다. 
            auto red = move(map,k,rx,ry);
            auto blue = move(map,k,bx,by);
            
            if(red.first == false && blue.first == false) break;
            
            if(red.second) redHole = true;
            if(blue.second) blueHole = true;
        }