[완전탐색] 백준 3085번 사탕 게임

www.acmicpc.net/problem/3085

3085번: 사탕 게임

수행시간 : 30분 + 30분(예외케이스 테스트시간)

 

BFS로 접근했다가, 세로는 세로로만 연속되고, 가로는 가로로만 연속되는 걸 count 해줘야 되기때문에 그냥 브루트포스로 풀었다. 역시 브루트포스는 처음 알고리즘 구상부분이 가장 힘든거 같다.. 

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

int n;
char map[51][51];
int maxCnt = 0;

void column(char arr[51][51], int s) { //세로
	for (int i = 0; i < s; i++) {
		int cnt = 1;
		for (int j = 0; j < s;j++) {
			if (arr[i][j] == arr[i][j + 1]) {
				cnt++;
			}
			else {
				if (cnt > maxCnt) {
					maxCnt = cnt;
				}
				cnt = 1;
			}
		}
	}
}
void row(char arr[51][51], int s) { //가로
	for (int i = 0;i < s;i++) {
		int cnt = 1;
		for (int j = 0;j < s;j++) {
			if (arr[j][i] == arr[j + 1][i]) {
				cnt++;
			}
			else {
				if (cnt > maxCnt) {
					maxCnt = cnt;
				}
				cnt = 1;
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n;i++) {
		for (int j = 0;j < n;j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < n;i++) {
		for (int j = 0; j < n-1;j++) {
			swap(map[i][j], map[i][j + 1]);
			column(map, n);
			row(map, n);
			swap(map[i][j + 1], map[i][j]);

			swap(map[j][i], map[j + 1][i]);
			column(map, n);
			row(map, n);
			swap(map[j + 1][i], map[j][i]);
		}
	}
	cout << maxCnt;
}