BaekJoon 3085번: 사탕 게임(C++)

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

3085번: 사탕 게임

풀이법

1) 구현과 브루트 포스로 풀어내는 문제였다. 난이도가 높은 문제는 아니었으나, 반례를 고려해야 하므로 꽤 많은 시간을 투자하였다.

2) check 함수는 상하좌우로 연결되어 있는 배열의 값과 현재 배열의 값을 바꾸는 함수이다. 모든 경우의 수를 고려해야 하기에 이 부분에서 시간을 줄이겠다고 vistied배열을 썻으나 실패하여서 제거하니 통과가 되었다. 모든 값은 처음 입력 값의 배열인 arr를 copy한 arr2배열을 활용하여 확인하였다.

3) countMax() 함수는 각 행과 각 열의 연속된 최대 값을 구하는 함수이다. 실제 배열이 50x50인 큰 사이즈의 배열이 아니기에 완전 탐색을 실시했으며 정답을 얻을 수 있었다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;

int n;
char arr[51][51];
char arr2[51][51];
bool visited[51][51];
int maxNum = 0;
int vx[4] = {1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
int countMax() // 행과 열의 내의 크기 최대 길이 구하는 함수.
{
	int ccnt = 0;
	int mMax = 0;
	int nMax = 0;
	for (int i = 0; i < n; i++)
	{
		ccnt = 1;
		for (int j = 0; j < n - 1; j++)
		{
			if (arr2[i][j] == arr2[i][j + 1])
			{
				ccnt++;
			}
			if (j == n - 2)
			{
				mMax = max(mMax, ccnt);
			}
			else if(arr2[i][j]!=arr2[i][j+1])
			{
				mMax = max(mMax, ccnt);
				ccnt = 1;
			}
		}
	}
	for (int j = 0; j < n; j++)
	{
		ccnt = 1;
		for (int i = 0; i < n - 1; i++)
		{
			if (arr2[i][j] == arr2[i + 1][j])
			{
				ccnt++;
			}
			if (i == n - 2)
			{
				nMax = max(nMax, ccnt);
			}
			else if(arr2[i][j]!=arr2[i+1][j])
			{
				nMax = max(nMax, ccnt);
				ccnt = 1;
			}
		}
	}
	return max(nMax, mMax);
}
void clearArr2()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			arr2[i][j] = arr[i][j]; //배열 카피;

}
int check(int a, int b)
{
	visited[a][b] = true;
	clearArr2();
	int checkMaxNum = 0; 
	for (int i = 0; i < 4; i++)
	{
		int nextX = a + vx[i];
		int nextY = b + vy[i];
		if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= n)
			continue;
		if (arr[a][b] != arr[nextX][nextY])
		{
			clearArr2();
			char temp = arr2[a][b];
			arr2[a][b] = arr2[nextX][nextY];
			arr2[nextX][nextY] = temp;
			int cnt=countMax(); //바꾼 것 개수 세기
			checkMaxNum = max(cnt, checkMaxNum);
		}
	}
	return checkMaxNum;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); j++)
		{
			arr[i][j] = s[j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int cnt = check(i,j);
			maxNum = max(maxNum, cnt);
		}
	}
	cout << maxNum;

}