[Silver 2] 9079 동전 게임

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

9079번: 동전 게임

 

이 문제는 행, 열, 대각선을 뒤집는 2^8개의 경우의 수를 모두 확인하면 해결할 수 있다.

 

9x9 크기의 동전의 상태를 0과 1로 나타내기 위해 T는 0, H는 1으로 나타낸다.

주어진 보기 중 H T T H T T T H H 는 100  100 001이 되며

비트로 바꿀 때 거꾸로 읽어 변환하기 때문에 100 001 001인 393이 된다.

 

동전을 뒤집는 값은

{ 000 000 111, 000 111 000, 111 000 000, 001 001 001, 010 010 010, 100 100 100, 100 010 001, 001 010 100 }

이 있다.

이는 세로 뒤집기 3가지, 가로 뒤집기 3가지, 대각 뒤집기 2가지이다.

이를 10진수로 변환하면 7, 56, 448, 73, 146, 292, 273, 84 이다.

 

위에서 변환한 비트를 사용해서 동전을 뒤집는 예이다.

 HTT    THH   <---
 HTT -> HTT : 가장 윗 부분 뒤집기
 THH    THH
 
 이를 숫자를 이용하여 계산을 해본다면 아래와 같음
  
 Before   : 110 001 001 -> 393
 가장 위를 뒤집는 값   : 000 000 111 -> 7
 After : 110 001 110 -> 398
 
 동전을 뒤집는 연산은 XOR 연산을 사용하면 된다.

 

동전의 상태는 queue 자료 구조에 삽입하여 저장한다.

처음 상태를 queue에 삽입하고 최소 경우를 뽑아야 하기 때문에 중복되는 경우가 없도록 visited 행렬을 사용한다.

이는 BFS 알고리즘을 사용하는 것이며, 완전 탐색을 BFS를 통해 구현하는 것이다.

 

동전을 뒤집기 위해 queue에 존재하는 동전 묶음 수만큼 반복을 진행한다.

queue의 front를 뽑고 위에서 정의한 8가지 bit에 대해 XOR 연산을 진행하고, 중복되지 않았다면 queue에 삽입한다.

 

동전이 모두 앞을 바라보는 경우는 111 111 111 이나, 000 000 000 인 경우이다. 

이를 10진수로 변환하면 0과 511인 경우이다. 

현재 queue의 front가 위 경우에 해당하면 반복을 멈추고 반복 횟수를 출력하면 된다.

 

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

int T;
int result = -1;

// 비트 마스크 = { 000 000 111, 000 111 000, 111 000 000, 001 001 001, 010 010 010,
// 100 100 100, 100 010 001, 001 010 100 }
int mask[] = { 7,56,448,73,146,292,273,84 };
bool visited[512] = { false };

int makeBit(string s) {
	int bit = 0;
	for (int i = 8; i >= 0; i--) {
		bit <<= 1;
		if (s[i] == 'H') bit |= 1;
	}
	return bit;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> T;
	for (int i = 0; i < T; i++) {
		string coin;
		char c;
		memset(visited, false, sizeof(visited));
		result = -1;

		for (int j = 0; j < 9; j++) {
			cin >> c;
			coin += c;
		}
		
		int bit = makeBit(coin);
		queue<int> q;
		q.push(bit);
		visited[bit] = true;

		bool sucess = false;

		while (!q.empty() && !sucess) {
			result++;
			int n = q.size();
			while (n--) {
				int current = q.front();
				q.pop();
				if (current == 0 || current == (1 << 9) - 1) {
					sucess = true;
					break;
				}
				for (int j = 0; j < 8; j++) {
					int nextState = current ^ mask[j];
					if (visited[nextState]) continue;
					visited[nextState] = true;
					q.push(nextState);
				}
			}
		}
		if (sucess) cout << result << '\n';
		else cout << -1 << '\n';
	}
	return 0;
}