[백준] 10472번 십자뒤집기

10472 십자뒤집기

문제

---

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

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

Figure D.1: 예제 입력

입력

---

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

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

출력

---

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

---

풀이) 

bfs와 set을 이용해 결과가 나올때까지 탐색해서 푼 문제이다. 

예전에 풀었던 주사위 회전 문제랑 비슷한것 같다.

3x3 보드를 9개의 원소를 가지는 배열로 만든다고 생각해보자.

칸이 칠해진 경우를 1, 칠해지지 않은 경우를 0이라고 할때 

나타날 수 있는 보드의 상태 개수 2^9개이다.

0	1	2
3	4	5
6	7	8

0

1

2

3

4

5

6

7

8

0이 뒤집어지면 → 1와 3도 뒤집어져야함

1가 뒤집어지면 → 0과 2, 4가 뒤집어져야함

...

7이 뒤집어지면 → 4, 6, 8이 뒤집어져야함

이런식으로 생각하고 풀었다. 

또한, 배열의 상태를 queue에 넣기 힘들므로 string으로 바꿔서 처리하였고 반복하지 않기 위해 set을 통해 중복되는 상태는 걸렀다.

코드)

#include <stdio.h>
#include<queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
 
//각 칸을 누를 때 뒤집힐 칸들(자기 자신도 포함해서)
vector <int> vec[9] = {
    {0, 1, 3}, {0, 1, 2, 4}, {1,2, 5},
    {0, 3, 4, 6}, {1, 3,4, 5, 7}, {2, 4, 5, 8},
    {3, 6, 7}, {4, 6,7, 8}, {5, 7,8}
};
 
int bfs(string s) {
    queue<string> qu;
    set<string> check;
    qu.push("000000000");
    check.insert("000000000");
    int time = 1;
    while (!qu.empty())
    {
        int size = qu.size();
        while (size--)
        {
            string here = qu.front();
            qu.pop();
            for (int i = 0; i < 9; i++) {
                string next = here;
                for (int j = 0; j < vec[i].size(); j++) {
                    //뒤집어 주는 과정
                    if (next[vec[i][j]] == '1') {
                        next[vec[i][j]] = '0';
                    }
                    else {
                        next[vec[i][j]] = '1';
                    }
                }
                if (check.find(next) != check.end()) continue;
                if (s == next) return time;
                qu.push(next);
                check.insert(next);
            }
        }
        time++;
    }
}
 
int main() {
    int test_case;
    scanf("%d", &test_case);
    getchar();
    while (test_case--)
    {
        string st = "";
        int idx = 1;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                char ch;
                scanf("%c", &ch);
                if (ch == '*') {
                    st += "1";
                }
                else {
                    st += "0";
                }
                idx++;
            }
            getchar();
        }
        if (st == "000000000") printf("0\n");
        else {
            printf("%d\n", bfs(st));
        }
    }
    return 0;
}

결과)