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

문제링크 : https://www.acmicpc.net/problem/10472

10472번: 십자뒤집기

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

vector<int>v[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}
}; //가짓수 9가지

int result = 0; 

void bfs(string s) 
{
   queue<string> q;
   set<string> check;
   q.push("000000000"); //초기 흰 보드
   check.insert("000000000"); //중복방지 체크용 흰보드

   int cnt = 1; //클릭 수
   while (!q.empty())
   {
      int size = q.size();
      while (size--) //각 케이스마다 탐색
      {
         string cur = q.front(); q.pop();
         for (int i = 0; i < 9; i++) 
         {
            string next = cur;
            for (int j = 0; j < v[i].size(); j++) 
            {
               if (next[v[i][j]] == '1') next[v[i][j]] = '0'; //바꾸기
               else next[v[i][j]] = '1';
            }
            if (check.find(next) != check.end()) continue; //next를 찾지 못하면 생략 (중복방지용)
            if (s == next) result = cnt; //목표를 찾았다면
            q.push(next); //다음 값
            check.insert(next); //다음 값
         }
      }
      cnt++;
   }
}
 
int main() 
{
   int T;
   cin >> T;
   
   while (T--)
   {
      string s = "";
      for (int i = 0; i < 3; i++) 
      {
         for (int j = 0; j < 3; j++) 
         {
            char c;
            cin >> c;
            if (c == '*') s += "1"; //검은색
            else s += "0"; //흰색
         }
      }
      if (s == "000000000") cout << 0 <<'\n'; //바꿀꺼 없음
      else 
      {
         bfs(s);
         cout << result << '\n';
      }  
   }
   return 0;
}

보드가 정해져 3x3으로 정해져있어서 길이가 9인 문자열을 이용한다.

처음에는 흰보드 이므로 000000000이고, 바꿔야하는 입력보드는 *일때 1, 아니면 0을 입력받아서 입력 문자열을 만든다.

만약 이 입력문자열이 000000000이면, 흰보드와 일치해서 바꿀 것이 없으므로 0을 출력하고 아니라면 bfs를 돌린다.

 

먼저 바꾸는 경우의 수는 

{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}

이렇게 9가지이다.

 

초기 흰 보드를 입력하고 여기에 중복방지를 체크하기 위한 set을 선언해준다.

여기서 이 set이 기존의 bfs에서 visited 배열 역할을 대신하는 것이다. (방문체크)

 

각 케이스마다 모두 완전탐색을 해야 하기에, 큐에 추가될때마다 따로 담아서 사이즈를 체크하고, 각각에 대해 탐색을 돌린다.

 

탐색해가면서 현재 진행중인 문자열을 계속해서 1과 0을 바꿔가면서 확인하고 만약 입력문자열과 같은 문자열을 찾으면 result에 저장해준다.

 

탐색 -> 바꾸기 -> 중복이 아니면 바꾼 값 큐에 추가 -> 반복