[Algorithm] Baekjoon 9079번 : 동전 게임

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

9079번: 동전 게임

struct Node
{
    bitset<9> bt;
    int count;
};
 
int targetNum = pow(2, 9) - 1;
bool visited[16000] = { false };
 
void checkAndPush(queue<Node>& q, bitset<9>& bt, int count)
{
    int tempNum = bt.to_ullong();
    if (visited[tempNum] == true) return;
    visited[tempNum] = true;
    q.push({ bt,count + 1 });
}
 
bool isAnswer(bitset<9>& bt)
{
    int num = bt.to_ulong();
 
    if (num == 0 || num == targetNum) return true;
    return false;
}
 
int BFS(bitset<9> bt)
{
    queue<Node> q;
    memset(visited, false, sizeof(visited));
    visited[bt.to_ulong()] = true;
    int answer = -1;
    
    q.push({ bt,0 });
 
    while (!q.empty())
    {
        bitset<9> curBT = q.front().bt;
        int curCount = q.front().count;
        q.pop();
 
        if (isAnswer(curBT))
        {
            answer = curCount;
            break;
        }
 
        for (int i = 0; i < 9; i+=3) // 행 뒤집기
        {
            bitset<9> temp = curBT;
 
            for (int j = i; j < i + 3; ++j) 
            {
                temp[j] = !temp[j];
            }
 
            checkAndPush(q, temp, curCount);
        }
 
        for (int i = 0; i < 3; ++i) // 열 뒤집기
        {
            bitset<9> temp = curBT;
 
            for (int j = i; j < 9; j+=3) 
            {
                temp[j] = !temp[j];
            }
 
            checkAndPush(q, temp, curCount);
        }
 
        bitset<9> temp = curBT;
        for (int i = 0; i < 9; i += 4) // 11->5 대각선
        {
            temp[i] = !temp[i];
        }
        checkAndPush(q, temp, curCount);
 
        temp = curBT;
        for (int i = 2; i < 7; i += 2) // 1->7 대각선
        {
            temp[i] = !temp[i];
        }
        checkAndPush(q, temp, curCount);
    }
 
    return answer;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int t;
    cin >> t;
 
    vector<int> answers;
 
    for (int i = 0; i < t; ++i)
    {
        bitset<9> bt;
        
        for (int r = 0; r < 3; ++r)
        {
            for (int c = 0; c < 3; ++c)
            {
                char tc;
                cin >> tc;
 
                bt[r * 3 + c] = tc == 'H' ? 0 : 1;
            }
        }
 
        answers.push_back(BFS(bt));
    }
 
    for (auto& temp : answers)
    {
        cout << temp << endl;
    }
}
 

쉬운 완전탐색문제인데, 표현을 할 때 비트마스킹으로하면 더 편하다.

각 상태는 2가지 (0과 1)로만 표현되기 때문에 이진수처럼 사용이 가능하고, 3*3판의 상태를 10진수의 형태로 표현하는게 가능하다.

해당 10진수로 방문체크를 하면서 행,열,대각선을 전부 뒤집어주는 완전탐색을 진행하면 된다.

비트마스킹 연습문제로 적절한 듯 하다.