백준 3085번 : 사탕 게임 - 완전탐색 C++

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

3085번: 사탕 게임

1.문제설명

1. 서로 다른 사탕이 있으면 바꾼다.

2. 모든 행과 열에서 연속되는 최대 사탕의 수를 구해본다.

3. 1과 2를 모든 영역에 대해 반복해야한다.

 

---

 

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, ans;
char arr[51][51];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void Count() {
	for (int i = 0; i < n; i++) {
		int comp = arr[i][0];
		int cnt = 1;
		for (int j = 1; j < n; j++) {
			if (comp == arr[i][j]) {
				cnt++;
			}
			else {
				comp = arr[i][j];
				ans = max(ans, cnt);
				cnt = 1;
			}
		}
		ans = max(ans, cnt);
	}

	for (int i = 0; i < n; i++) {
		int comp = arr[0][i];
		int cnt = 1;
		for (int j = 1; j < n; j++) {
			if (comp == arr[j][i]) {
				cnt++;
			}
			else {
				comp = arr[j][i];
				ans = max(ans, cnt);
				cnt = 1;
			}
		}
		ans = max(ans, cnt);
	}

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			arr[i][j] = s[j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {

			for (int k = 0; k < 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];

				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (arr[i][j] != arr[nx][ny]) {
					swap(arr[i][j], arr[nx][ny]);
					Count();
					swap(arr[i][j], arr[nx][ny]);
				}
			}
		}
	}
	
	cout << ans << '\n';


	return 0;
}

백준 3085번 사탕게임