[백준]1285 동전 뒤집기

문제

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

1285번: 동전 뒤집기

 

풀이

처음엔 동전의 배열을 노드로 하는 그래프의 DFS 탐색으로 풀었다. 

현재 노드는 현재 동전 배열이고, 인접한 노드들은 모든 행, 모든 열을 뒤집는 경우의 동전 배열이다.

이런 식으로 풀어도 답은 나오지만, 메모리 초과 혹은 시간초과가 발생한다.

 

결국 다른 블로그 글을 보고 깨달았다.

https://please-amend.tistory.com/175

백준 1285번 동전 뒤집기 - C++ 풀이

풀이 방법은

우선 행들을 먼저 뒤집고, 이후 T가 최소가 되도록 열을 뒤집고, T가 가장 적었던 경우를 기록하는 것이다.

이 때, 뒤집을 행들은 모든 경우에 대해 계산해 주어야 한다.

예를 들어 N이 3이면

0번째 행을 뒤집는 경우, 1번째 행을 뒤집는 경우, 2번째 행을 뒤집는 경우,

0,1번째 행을 뒤집는 경우, 1,2번째 행을 뒤집는 경우, 0,2번째 행을 뒤집는 경우 

총 6가지 경우에 대해 계산해야 한다. 나는 이 때 뒤집는 행들에 대한 정보를 flipRow라는 int형 변수에 비트연산으로 담아서 전달했다.

행들을 뒤집은 이후, 각 열마다 T가 몇 개인지 세고 T가 H보다 더 많다면 해당 열을 뒤집는다. 

그리고 T의 갯수를 세면 flipRow에 담긴 뒤집은 행들에 대해서 가장 적은 T의 갯수를 알 수 있다.

이 작업을 모든 flipRow에 대해 진행하여 가장 적은 T를 찾는다.

 

참고로, 열 먼저 뒤집고 나중에 행을 뒤집어 주어도 된다.

 

코드

// CodeTest.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;
int N;
char C;
int answer;
vector<bool>board;


int CountTAfterFlip(vector<bool> _board, int rowsToFlip)
{
	int ret = 0;

		for (int c = 0; c < N; c++)
		{
			int headCount = 0;
			for (int r = 0; r < N; r++)
			{
				if ((rowsToFlip & (1 << r)) != 0)
					_board[r * N + c] = !_board[r * N + c];
				headCount = _board[r * N + c] ? ++headCount : headCount;
			}
			ret += min(headCount, N-headCount);
		}
	return ret;
}

int main()
{
	cin >> N;
	board.resize(N*N);
	for (size_t i = 0; i < N * N; i++)
	{
		cin >> C;
		board[i] = C == 'H' ? true : false;
	}

	answer = N * N;
	
	for (int flipRow = 0; flipRow < (1 << N); flipRow++)
	{
		answer = min(answer, CountTAfterFlip(board,flipRow));
	}

	
	cout << answer;
}