[G5] 백준 10472번 십자뒤집기 C++ 비트마스킹, BFS, 브루트포스 알고리즘

리뷰

 

3 * 3 도형을 반전시켜 모든 땅을 흰색으로 만드는 문제

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

 

전역 변수

• tc, target : 테스트케이스의 개수tc, 각 테케마다 초기 도형의 비트 정보target
• lst : 초기 맵 상태를 얻어올 문자열 배열, 3 * 3크기이므로 크기는 3이다.
• dx, dy : 비트 반전을 시킬 구간의 방향 배열, 상하좌우 및 제자리를 포함하여 총 5개이다.
• v : 비트마스킹 시 방문 여부를 저장할 배열 9개의 상태를 저장해야 하므로 2^9보다 크게 설정한다.
• Pos : 큐 내부에서 현재 비트정보와 변환 횟수를 저장하여 사용할 구조체

 

함수

1. getTarget

void getTarget()

 

테스트케이스에서 입력된 도형의 비트 정보를 target변수에 저장하기 위한 함수

1. 이전 테케의 기록을 지우기 위해 target을 0으로 초기화 해준다.
2. 3 * 3맵정보를 탐색하며 *가 존재한다면 해당 위치에 따라 비트를 시프트연산하여 target에 더해준다.

 

2. togle

int togle(int cx, int cy, int bits)

 

현재 위치에서 상하좌우 및 제자리를 반전시킨 후의 비트정보를 리턴하는 함수

1. 매개변수 bits에 현재 위치로부터 4방향 및 현재 위치의 비트 정보를 반전시켜준다.
2. 모든 반전 작업이 마친 후에 bits를 리턴해 준다.

 

3. solution

int solution()

 

BFS를 통해 target에 도달하기 까지의 비트반전 횟수의 최소값을 리턴하는 함수

1. Pos타입의 구조체 q를 초기화 해주고 탐색 초기상태인 0과 횟수도 0을 큐에 넣어준다.
2. memset메서드를 통해 이전에 사용했던 방문 배열 내의 값을 다시 0으로 모두 초기화 해준다.
3. q가 빌때까지 while문을 수행하여 현재 큐에서 값을 빼내주고 비트 정보 val과 cnt를 참조해 준다.
4. 만약 val값이 target과 일치한다면 cnt를 리턴해 주면 된다.
5. 일치하지 않을 경우 3 * 3크기의 맵을 순회하며 각 위치를 togle함수를 통해 변환된 비트값을 new_val에 저장한다.
6. 만약 new_val이 방문하지 않은 비트값인 경우 new_val을 방문처리 해준다.
7. 이후 new_val과 cnt + 1을 큐에 삽입하여 계속 탐색해 준다.

 

문제풀이

1. tc를 입력 받고 tc번의 반복문을 개행해 준다.
2. 맵 정보를 3줄의 문자열로 입력 받아 lst배열의 각 인덱스에 저장해 준다.
3. getTarget함수를 통해 초기 도형의 비트값을 target변수에 저장해 준다.
4. solution함수를 실행하고 리턴받은 값을 출력해 주고 줄바꿈 해준다.

 

참고 사항

각 테스트 케이스 마다 target과 방문배열을 초기화 해주어야 한다.

 

 

정답 코드

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

int tc, target;
string lst[3];

int dx[] = { 0, 0, 0, 1, -1 };
int dy[] = { 0, 1, -1, 0, 0 };
int v[513];

struct Pos {
	int bits, cnt;
};

void getTarget() {
	target = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (lst[i][j] == '*') target += (1 << i * 3 + j);
		}
	}
}

int togle(int cx, int cy, int bits) {
	for (int i = 0; i < 5; i++) {
		int nx = cx + dx[i], ny = cy + dy[i];
		if (0 <= nx && nx < 3 && 0 <= ny && ny < 3) bits ^= 1 << nx * 3 + ny;
	}
	return bits;
}

int solution() {
	queue<Pos> q;
	q.push({0, 0});
	memset(v, 0, sizeof(v));

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int val = pos.bits, cnt = pos.cnt;
		if (val == target) return cnt;

		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				int new_val = togle(i, j, val);
				if (!v[new_val]) {
					v[new_val] = cnt + 1;
					q.push({ new_val, cnt + 1 });
				}
			}
		}
	}
}

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

	cin >> tc;
	while (tc--) {
		for (int i = 0; i < 3; i++) cin >> lst[i];
		getTarget();
		cout << solution() << "\n";
	}
}