4613. 러시아 국기 같은 깃발

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQl9TIK8qoDFAXj&categoryId=AWQl9TIK8qoDFAXj&categoryType=CODE

SW Expert Academy

 

하나씩 바꿔가면서 DFS가 아니고 행을 3개로 분리하는 로직을 생각해 내면 끝.

 

#include<iostream>
#include<string>
#include<vector>
using namespace std;
string arr[50];
int N, M;
int mina;
vector<int> vec;

void DFS(int cur)
{
	if (cur == 2)
	{
		vec.push_back(N - 3 - vec[0] - vec[1]);
		
		int con = 0;
		
		for (int i = 0; i < vec[0] + 1; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (arr[i][j] != 'W')
				{
					con++;
				}
			}
			
		}

		for (int i = vec[0] + 1; i < vec[0] + 1 + vec[1] + 1; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (arr[i][j] != 'B')
				{
					con++;
				}
			}
		}

		for (int i = vec[0] + 1 + vec[1] + 1; i < vec[0] + 1 + vec[1] + 1+ vec[2] + 1; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (arr[i][j] != 'R')
				{
					con++;
				}

			}
		}


		vec.pop_back();

		if (con < mina)
		{
			mina = con;
		}

		return;
	}
	else
	{
		for (int i = 0; i <= N - 3 - vec[0]; i++)
		{
			vec.push_back(i);
			DFS(cur+1);
			vec.pop_back();

		}
	}

}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N >> M;

		mina = 987654321;
		

		for (int i = 0; i < N; i++)
		{
			cin >> arr[i];
			
		}

		
		for (int i = 0; i <= N - 3; i++)
		{
			vec.push_back(i);
			DFS(1);
			vec.pop_back();
		}
		
		cout << "#" << test_case << " " << mina << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}