6731. 홍익이의 오델로 게임

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWefzFeq5P8DFAUh

SW Expert Academy

 

 

DFS로 풀면 시간초과 및 종료 시점에 대한 지정이 힘들다.

규칙을 찾아서 푸는 것이 관건인 문제.

 

어떤 모양이 주어졌을 때, 그 모양을 만들기 위해서 최소로 뒤집어야 하는 좌표는 i,j에 있어서 해당 열과 행의 

검은색의 개수의 합이 홀수인 좌표이다.

 

따라서 각 열과 행의 검은색 개수를 구하고

이때 i,j 좌표 자체가 검은색이면 행과 열의 개수 합에서 -1을 해줘야 함.

 

홀수인 좌표의 개수를 카운트해서 출력하면 끝.

 

#include<iostream>
#include<string.h>
#include<cmath>
using namespace std;




int N;
int mina;
char arr[1000][1000];
int row[1000];
int col[1000];




int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N;
		mina = 987654321;


		memset(row, 0, sizeof(row));
		memset(col, 0, sizeof(col));
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> arr[i][j];
				
			}
		}

		

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (arr[i][j] == 'B')
				{
					row[i]++;
					col[j]++;
				}

			}
		}


		

		int result = 0;

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				int black;
				if (arr[i][j] == 'B')
				{
					black = row[i] + col[j] - 1;
				}
				else
				{
					black = row[i] + col[j];
				}

				if (black % 2)
				{
					result++;
				}
			}
		}

		cout << "#" << test_case << " " << result << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}