[백준] 10472번 : 십자뒤집기 (C++)

10472번 : 십자뒤집기

---

문제)

당신에게 3x3 크기의 보드가 주어진다. 각각의 칸은 처음에 흰색 혹은 검은색이다. 만약 당신이 어떤 칸을 클릭한다면 당신이 클릭한 칸과 그 칸에 인접한 동서남북 네 칸이 (존재한다면) 검은색에서 흰색으로, 혹은 흰색에서 검은색으로 변할 것이다.

당신은 모든 칸이 흰색인 3x3 보드를 입력으로 주어지는 보드의 형태로 바꾸려고 한다. 보드를 회전시킬수는 없다.

 

 

 

입력 :

첫 줄에는 테스트 케이스의 숫자 P(0 < P ≤ 50)이 주어진다.

각각의 테스트 케이스에 대해서 세 줄에 걸쳐 한 줄에 세 글자씩이 입력으로 들어온다. "*"은 검은색을 뜻하며 "."은 흰색을 뜻한다.

 

 

 

출력 :

각각의 테스트 케이스에 대해서 흰 보드를 입력에 주어진 보드로 바꾸는 데 필요한 최소 클릭의 횟수를 구하여라.

 

 

 

 

 

 

풀이)

 

#include <iostream>
#include <queue>
#include <vector>
#include <bitset>
#include <string>
 
 
using namespace std;
 
int p;
int visited[1000];
 
// 주어진 보드를 비트마스킹을 이용하여 10진수로 바꾸었다.
unsigned long convert(vector<string> vec)
{
    /*
    
    *..        100
    **.  => 110     =>  100110100 =>  308
    *..        100
    
    */
 
    string temp = "";
 
    for (auto nxt : vec)
    {
        temp += nxt;
    }
 
    bitset<9> bit(temp);
 
    return bit.to_ulong();
}
 
// 해당 버튼을 클릭했을 때 변화하는 배열
vector<string> tapping(int a, int b, vector<string> board)
{
    int dx[] = { 0, 1, -1, 0, 0 };
    int dy[] = { 0, 0, 0, -1, 1 };
 
    for (int i = 0; i < 5; i++)
    {
        int nx = a + dx[i];
        int ny = b + dy[i];
 
        if (0 > nx || nx >= 3) continue;
        if (0 > ny || ny >= 3) continue;
        
        if (board[nx][ny] == '0') board[nx][ny] = '1';
        else if (board[nx][ny] == '1') board[nx][ny] = '0';
    }
 
    return board;
}
 
 
int bfs(vector<string> goal)
{
    int t = 0;
    vector<string> start_board(3, "000");
 
    queue<vector<string>> q;
    q.push(start_board);
    visited[convert(start_board)] = 1;
 
    while (!q.empty())
    {
        int loop = q.size();
        
        for (int _ = 0; _ < loop; _++)
        {
            vector<string> board = q.front();
            q.pop();
            
            // 목표하는 배열과 같다면 time를 리턴하면 됨.
            if (board == goal) return t;
 
            // 모든 버튼 클릭에 대하여 bfs를 진행한다.
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    vector<string> nxt = tapping(i, j, board);
                    int nxt_binary = convert(nxt);
 
                    if (!visited[nxt_binary])
                    {
                        q.push(nxt);
                        visited[nxt_binary] = 1;
                    }
                }
            }
        }
 
        t++;
    }
}
 
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> p;
 
    for (int _ = 0; _ < p; _++)
    {
        vector<string> vec;
        fill(visited, visited + 1000, 0);
 
        for (int i = 0; i < 3; i++)
        {
            string temp = "";
            char t;
            for (int j = 0; j < 3; j++)
            {    
                cin >> t;
                if (t == '*') temp += "1";
                else if (t == '.') temp += "0";
            }
            vec.push_back(temp);
        }
 
        cout << bfs(vec) << '\n';
    }
 
    return 0;
}

---

출처 : https://www.acmicpc.net/problem/10472 

10472번: 십자뒤집기