백준 알고리즘 문제 풀이 c/c++ -3085-

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

• 완전탐색으로 모든 좌표에서 최대의 경우를 구함
• 현재 좌표 기준 인접한 오른쪽, 아래쪽과 바꾸며 비교를 하면 상하좌우 4방향 모두 검사 할 필요가 없다

#include <stdio.h>
#include <algorithm>

using namespace std;

int n;
char arr[55][55];

int ANS = 0;  // 제일 긴 경우의 값

int main() {

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf(" %c", &arr[i][j]);
		}
	}

	


	// 좌표 별로 돌면서 
	// 1. 원래 상태에서 최대
	// 2. 오른쪽과 바꾼 상태
	// 3. 아래쪽과 바꾼 상태
	// 위 3개의 경우를 살펴본다

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {   // 모든 좌표를 살핀다
			
			char check = arr[i][j];

			int cnt = 0;

			// 1. 원래 상태에서 최대값 찾기
			  // 오른쪽 보기
			for (int k = j; k < n; k++) {
				if (arr[i][k] == check)
					cnt++;
				else
					break;
			}
			if (cnt > ANS)
				ANS = cnt;

			cnt = 0;

			  // 아래쪽 보기
			for (int k = i; k < n; k++) {
				if (arr[k][j] == check)
					cnt++;
				else
					break;
			}
			if (cnt > ANS)
				ANS = cnt;

			cnt = 0;

			//////////////
			char temp = arr[i][j];  
			//////////////

			// 2. 오른쪽과 바꾼 상태
			
			if (j < n - 1) { 
				// 임시로 바꾸기
				arr[i][j] = arr[i][j + 1];
				arr[i][j + 1] = temp;
			
				// [0][j] 부터 하나씩 밑으로 검사하기
				for (int k = 0; k < n; k++) {
				
					char a = arr[k][j];
					for (int t = k; t < n; t++) {
						if (arr[t][j] == a)
							cnt++;
						else
							break;
					}
					if (cnt > ANS)
						ANS = cnt;
					
					cnt = 0;
				}


				// [0][j+1] 부터 하나씩 밑으로 검사하기
				for (int k = 0; k < n; k++) {

					char a = arr[k][j+1];
					for (int t = k; t < n; t++) {
						if (arr[t][j+1] == a)
							cnt++;
						else
							break;
					}
					if (cnt > ANS)
						ANS = cnt;

					cnt = 0;
				}


				// [i][0] 부터 오른쪽으로 하나씩 검사하기
				for (int k = 0; k < n; k++) {

					char a = arr[i][k];

					for (int t = k; t < n; t++) {
						if (arr[i][t] == a)
							cnt++;
						else
							break;
					}
					if (cnt > ANS)
						ANS = cnt;

					cnt = 0;
				}

			

				//원래대로 돌리기
				arr[i][j + 1] = arr[i][j];
				arr[i][j] = temp;
			}


			// 3. 아래쪽과 바꾼 상태
			if (i < n - 1) {
				arr[i][j] = arr[i + 1][j];
				arr[i + 1][j] = temp;
			
			// [i][0] 부터 하나씩 오른쪽으로 검사하기
				for (int k = 0; k < n; k++) {

					char a = arr[i][k];
					for (int t = k; t < n; t++) {
						if (arr[i][t] == a)
							cnt++;
						else
							break;
					}
					if (cnt > ANS)
						ANS = cnt;

					cnt = 0;
				}


			// [i+1][0] 부터 하나씩 오른쪽으로 검사하기
				for (int k = 0; k < n; k++) {

					char a = arr[i+1][k];
					for (int t = k; t < n; t++) {
						if (arr[i+1][t] == a)
							cnt++;
						else
							break;
					}
					if (cnt > ANS)
						ANS = cnt;

					cnt = 0;
				}

			// [0][j] 부터 하나씩 밑으로 검사하기
				for (int k = 0; k < n; k++) {

					char a = arr[k][j];
					for (int t = k; t < n; t++) {
						if (arr[t][j] == a)
							cnt++;
						else
							break;
					}
					if (cnt > ANS)
						ANS = cnt;

					cnt = 0;
				}

		

			// 원래대로 돌리기
				arr[i + 1][j] = arr[i][j];
				arr[i][j] = temp;
			}

		}
	}


	printf("%d\n", ANS);


	return 0;
}