BOJ 3085 사탕게임

BOJ 3085 사탕게임

문제링크 : <https://www.acmicpc.net/problem/3085

요약

주어진 문자(사탕색깔)로 이루어진 배열중에 딱한번 자신과 인접해있는 색이다른 사탕과 교환했을때 가로나, 세로로 인접해있는 같은 색의 사탕의 연속갯수가 가장 큰 값을 구하시오. (예제 출력을 보면 알수 있지만 한줄의 가로줄, 한줄의 세로줄이다!)

풀이

구현이 좀 까다롭다.. 사탕 보드의 개수가 최대 50x50이고 인접한 칸끼리 바꿀수 있는 최대 경우의 수도 50x49x2임으로 완전탐색으로 모두 바꿀수 있는 경우를 전부 해보고 바꿀떄마다 포문으로 바뀌는 사탕이 포함된 가로 세로줄을 확인해서 인접한 최대갯수를 확인해주면 된다.

코드

#include<iostream>
using namespace std;
int n,change,cnt, big;
char arr[51][51];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf(" %1c", &arr[i][j]);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n-1; j++) {
				change = arr[i][j];
				arr[i][j] = arr[i][j+1];
				arr[i][j+1] = change;
			cnt = 1;
			for (int k = 0; k < n-1; k++) {
				if (arr[i][k] == arr[i][k+1]) {
					cnt++;
					if (big < cnt)big = cnt;
				}
				else cnt = 1;
			}
			cnt = 1;
			for (int k = 0; k < n-1; k++) {
				if (arr[k][j] == arr[k+1][j]) {
					cnt++;
					if (big < cnt)big = cnt;
				}
				else cnt = 1;
			}
			cnt = 1;
			for (int k = 0; k < n; k++) {
				if (arr[k][j+1] == arr[k+1][j+1]){
					cnt++;
					if (big < cnt)big = cnt;
				}
				else cnt = 1;
			}
			arr[i][j+1] = arr[i][j];
			arr[i][j] = change;
		}
	}
	for (int j = 0; j < n; j++) {
		for (int i = 0; i < n-1; i++) {
				change = arr[i][j];
				arr[i][j] = arr[i+1][j];
				arr[i+1][j] = change;
			
			cnt = 1;
			for (int k = 0; k < n - 1; k++) {
				if (arr[k][j] == arr[k+1][j]) {
					cnt++;
					if (big < cnt)big = cnt;
				}
				else cnt = 1;
			}
			cnt = 1;
			for (int k = 0; k < n - 1; k++) {
				if (arr[i][k] == arr[i][k+1]) {
					cnt++;
					if (big < cnt)big = cnt;
				}
				else cnt = 1;
			}
			cnt = 1;
			for (int k = 0; k < n; k++) {
				if (arr[i+1][k] == arr[i+1][k+1]) {
					cnt++;
					if (big < cnt)big = cnt;
				}
				else cnt = 1;
			}
			arr[i+1][j] = arr[i][j];
			arr[i][j] = change;
		}
	}
	printf("%d", big);
}