백준 3085

백준 3085 : 사탕 게임

구현해야 할 기능
1. 입력받기
2. 하나하나 다 바꿔가면서
3. 바꿀때마다 그때의 최대값을 출력
4. 시간 복잡도는 O(N^4), N=50이라서 가능

정답 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;
char candy[51][51];
int maxCnt;
int ans;

void input() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin>>n;
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			cin>>candy[i][j];
		}
	}
}

void printCandy(char candy[51][51]) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			cout<<candy[i][j];
		}
		cout<<'\n';
	}
}

//get longest sequence in array
void getLongest(char candy[51][51]) {
	int cnt_horizontal, cnt_vertical;
	
	//check horizontal
	for(int i=0; i<n; i++) {
		cnt_horizontal=1;
		for(int j=0; j<n; j++) {
			if(candy[i][j] == candy[i][j+1]) {
				cnt_horizontal++;
			}
			else {
				if(cnt_horizontal>maxCnt) {
					maxCnt=cnt_horizontal;
				}
				cnt_horizontal=1;
			}
		}
	}
		
	//check vertical
	for(int i=0; i<n; i++) {
		cnt_vertical=1;
		for(int j=0; j<n; j++) {
			if(candy[j][i] == candy[j+1][i]) {
				cnt_vertical++;
			}
			else {
				if(cnt_vertical>maxCnt) {
					maxCnt = cnt_vertical;
				}
				cnt_vertical=1;
			}
		}
	}
	
//	cout<<"maxCnt: "<<maxCnt<<'\n'<<'\n';
}

//swap and count by row
void swapByRow() {
	for(int i=0; i<n; i++) {
		for(int j=0; j<n-1; j++) {
			//swap
			int temp = candy[i][j];
			candy[i][j] = candy[i][j+1];
			candy[i][j+1] = temp;
			
//			printCandy(candy);
			getLongest(candy);
			
			//swap
			int temp1 = candy[i][j];
			candy[i][j] = candy[i][j+1];
			candy[i][j+1] = temp1;
		}
	}
	
}

//swap and count by column
void swapByColumn(int j) {
	for(int i=0; i<n-1; i++) {
		//swap
		int temp = candy[i][j];
		candy[i][j] = candy[i+1][j];
		candy[i+1][j] = temp;
		
//		printCandy(candy);
		getLongest(candy); //get max
		
		//swap
		int temp1 = candy[i][j];
		candy[i][j] = candy[i+1][j];
		candy[i+1][j] = temp1;
	}
}



int main() {	

	input();
	
	swapByRow();
	
	for(int j=0; j<n; j++) {
		swapByColumn(j);
	}
	
	cout<<maxCnt<<'\n';
	
	
	return 0;
}