[백준] 1285 동전 뒤집기⭐

백준 1285 동전 뒤집기

• https://www.acmicpc.net/problem/1285

틀린 풀이 1

• bfs로 접근

• 메모리 초과

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <set>
#include <algorithm>
using namespace std;

int N;
vector<int> board;

inline int countTail(vector<int> curBoard) {
	int tail = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if ((curBoard[i] & (1 << j)) == 0) tail++;
		}
	}
	return tail;
}

int getMinTail() {
	int minTail = N * N;

	queue<vector<int>> q;
	q.push(board);
	
	set<vector<int>> visited;

	while (!q.empty()) {
		vector<int> curBoard = q.front();
		q.pop();

		if (visited.find(curBoard) != visited.end()) continue;
		visited.insert(curBoard);

		//현재 보드에 동전 뒷면의 개수 세기
		int curTail = countTail(curBoard);
		minTail = min(minTail, curTail);

		vector<int> nextBoard;
		for (int i = 0; i < N; ++i) {
			//i번째 행 뒤집기
			nextBoard.clear();
			nextBoard.assign(curBoard.begin(), curBoard.end());
			//i번째 행 toggle
			nextBoard[i] = curBoard[i] ^ ((1 << N) - 1);

			if (visited.find(nextBoard) == visited.end())
				q.push(nextBoard);

			//i번째 열 뒤집기
			nextBoard.clear();
			nextBoard.assign(curBoard.begin(), curBoard.end());
			for (int j = 0; j < N; ++j) {
				//j번째 행의 i번째 열 toggle
				nextBoard[j] = nextBoard[j] ^ (1 << i);
			}
			if (visited.find(nextBoard) == visited.end())
				q.push(nextBoard);

		}
	}
	
	return minTail;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; ++i) {
		string input;
		cin >> input;

		//한 행 비트마스크로 표현
		//앞면 H = 1, 뒷면 T = 0
		int bitmask = 0;
		for (int i = 0; i < N; ++i) {
			if (input[i] == 'H')
				bitmask |= (1 << i);
		}
		board.push_back(bitmask);
	}

	cout << getMinTail();
	return 0;
}

틀린 풀이 2

• 각 동전의 상태에 영향을 미칠 수 있는 동작:
  1. 동전이 속한 행 뒤집기
  2. 동전이 속한 열 뒤집기
• 이 2 가지 동작은 서로 독립적이다

HHT                 THT                 HTH
THH -(1열 뒤집기)->  HHH -(1행 뒤집기)->  HHH  
THT                 HHT                 HHT

HHT                 TTH                 HTH
THH -(1행 뒤집기)->  THH -(1열 뒤집기)->  HHH  
THT                 THT                 HHT

행과 열을 뒤집는 순서에 상관 없이 결과 동일!

• 동전을 뒤집을 행과 동전을 뒤집을 열: rowBitmask, colBitmask로 표현

• N 최대 20
  -> 이중 for문 (2^20) $*$ (2^20)번 실행됨
  -> 시간 초과

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

	vector<int> board;
	for (int i = 0; i < N; ++i) {
		string input;
		cin >> input;

		//한 행 비트마스크로 표현
		//앞면 H = 1, 뒷면 T = 0
		int bitmask = 0;
		for (int i = 0; i < N; ++i) {
			if (input[i] == 'H')
				bitmask |= (1 << i);
		}
		board.push_back(bitmask);
	}

	int minTail = N * N;
	
	//rowBitmask: 뒤집을 행 1, 뒤집지 않을 행 0
	//colBitmask: 뒤집을 열 1, 뒤집지 않을 열 0
	for (int rowBitmask = 0; rowBitmask < (1 << N); rowBitmask++) {
		for (int colBitmask = 0; colBitmask < (1 << N); colBitmask++) {

			vector<int> newBoard(board.begin(), board.end());
			
			for (int i = 0; i < N; ++i) {
				//행 뒤집기
				if (rowBitmask & (1 << i)) {
					newBoard[i] ^= ((1 << N) - 1);
				}
				//열 뒤집기
				if (colBitmask & (1 << i)) {
					for (int j = 0; j < N; ++j) {
						newBoard[j] ^= (1 << i);
					}
				}
			}

			//뒷면의 개수 세기
			int tail = 0;
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < N; ++j) {
					if ((newBoard[i] & (1 << j)) == 0)
						tail++;
				}
			}
			minTail = min(minTail,tail);
		}
	}

	cout << minTail;
	return 0;
}

풀이

• 동전을 뒤집을 열은 모든 경우의 수를 비트마스크로 만들 필요 X
  -> 동전을 뒤집을 행만 bitmask로 표현
  -> bitmask에 표현된 대로 동전의 행들을 뒤집은 후, 동전의 뒷면이 적어지도록 각 열을 뒤집으면 된다

• 시간초과 해결됨!

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

	vector<int> board;
	for (int i = 0; i < N; ++i) {
		string input;
		cin >> input;

		//한 행 비트마스크로 표현
		//앞면 H = 1, 뒷면 T = 0
		int bitmask = 0;
		for (int i = 0; i < N; ++i) {
			if (input[i] == 'H')
				bitmask |= (1 << i);
		}
		board.push_back(bitmask);
	}

	int minTail = N * N;
	
	//bitmask: 뒤집을 행 1, 뒤집지 않을 행 0
	for (int bitmask = 0; bitmask < (1 << N); bitmask++) {
		vector<int> newBoard(board.begin(), board.end());
			
		//행 뒤집기
		for (int i = 0; i < N; ++i) {
			if (bitmask & (1 << i)) {
				newBoard[i] ^= ((1 << N) - 1);
			}
		}

		//뒷면의 개수 세기
		int tail = 0;

		//뒷면의 개수 적어지도록 열 뒤집기
		for (int i = 0; i < N; ++i) {
			
			//뒤집지 않았을 때 해당 열의 뒷면 수
			int colTail = 0;
			for (int j = 0; j < N; ++j) {
				if ((newBoard[j] & (1 << i)) == 0) 
					colTail++;
			}

			//뒤집었을 때 해당 열의 뒷면 수 = N - colTail
			colTail = min(colTail, N - colTail);

			//해당 열 뒤집었다고 치고 전체 뒷면의 개수에 더해줌
			tail += colTail;
		}
		minTail = min(minTail,tail);
	}

	cout << minTail;
	return 0;
}

📌참고자료

• 백준 1285 동전 뒤집기
  https://staticvoidlife.tistory.com/144