[C++] 백준 3085번 사탕 게임

 

1) 문제설명

백준 Online Judge 3085번 사탕 게임

 

2) 아이디어

가로/세로 인접한 글자가 다를 때마다 바꾸고 인접한 문자의 개수를 센다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int n;
char arr[51][51];

int check() { // 가로 세로 중복확인 함수
	int maxt = 0;
	int v1_cnt = 0, h1_cnt = 0;
	for (int i = 0; i < n; i++) {
		int v_cnt = 0, h_cnt = 0;
		// 가로 중복확인
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == arr[i][j + 1]) {
				v_cnt++;
			}
			else {
				v_cnt = 0;
			}
			v1_cnt = max(v_cnt, v1_cnt);
		}
		// 세로 중복확인
		for (int j = 0; j < n; j++) {
			if (arr[j][i] == arr[j + 1][i]) {
				h_cnt++;
			}
			else {
				h_cnt = 0;
			}
			h1_cnt = max(h_cnt, h1_cnt);
		}
		maxt = max(maxt, max(v1_cnt, h1_cnt));
	}
	return maxt;
}

int main() {
	int result = 0;
	int result1 = 0, result2 = 0;
	cin >> n;
	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 (j + 1 < n) {
				if (arr[i][j] != arr[i][j + 1]) { // 가로가 다르면 위치를 바꾼다.
					char temp;
					temp = arr[i][j];
					arr[i][j] = arr[i][j + 1];
					arr[i][j + 1] = temp;
				}

				int maxt = check() + 1; // 가로/세로 중복 갯수 세기
				result1 = max(result1, maxt);

				char temp = arr[i][j]; // 다했으면 다시 원위치
				arr[i][j] = arr[i][j + 1];
				arr[i][j + 1] = temp;
			}
			
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (j + 1 < n) {
				if (arr[j][i] != arr[j+1][i]) { // 세로가 다르면 위치를 바꾼다.
					char temp;
					temp = arr[j][i];
					arr[j][i] = arr[j+1][i];
					arr[j+1][i] = temp;
				}

				int maxt = check() + 1; // 가로/세로 중복 갯수 세기
				result2 = max(result2, maxt);
				
				char temp;
				temp = arr[j][i];
				arr[j][i] = arr[j + 1][i];
				arr[j + 1][i] = temp;
			}

		}
	}
	result = max(result1, result2);
	cout << result;
	
}