[ 백준 3085 ] 사탕 게임 (C++)

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

3085번: 사탕 게임

 

제한 시간이 1초로 널널해서 모든 경우의 수를 다 고려해줬다. 모든 칸에 대해 가로/세로 다 swap 해주고 그때의 연속 사탕 수를 확인했다. 코드에서 check() 함수는 최대 연속 사탕수를 반환해주는 함수다. 유의할 점은 swap 해주고 다시 원위치 시켜줘야 하므로 다시 swap을 해줘야 한다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int N;
char map[50][50];

int check() {
	int Max = 0;
	char now;
	int cnt;

	// 1. 가로
	for (int row = 0; row < N; row++) {
		now = map[row][0];
		cnt = 1;
		for (int col = 1; col < N; col++) {
			if (now == map[row][col])
				cnt++;
			else {
				now = map[row][col];
				Max = max(Max, cnt);
				cnt = 1;
			}
		}
		Max = max(Max, cnt);
	}

	// 2. 세로
	for (int col = 0; col < N; col++) {
		now = map[0][col];
		cnt = 1;
		for (int row = 1; row < N; row++) {
			if (now == map[row][col])
				cnt++;
			else {
				now = map[row][col];
				Max = max(Max, cnt);
				cnt = 1;
			}
		}
		Max = max(Max, cnt);
	}

	return Max;
}

int get_ans() {
	int Max = 0;

	// 1. 가로
	for (int row = 0; row < N; row++) {
		for (int col = 0; col < N - 1; col++) {
			swap(map[row][col], map[row][col + 1]);
			Max = max(check(), Max);
			swap(map[row][col], map[row][col + 1]);
		}
	}

	// 2. 세로
	for (int col = 0; col < N; col++) {
		for (int row = 0; row < N - 1; row++) {
			swap(map[row][col], map[row + 1][col]);
			Max = max(check(), Max);
			swap(map[row][col], map[row + 1][col]);
		}
	}

	return Max;
}

 int main() {

	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];

	cout << get_ans() << endl;

	
	return 0;
}