C++ 백준 3085번

백준 3085번 www.acmicpc.net/problem/3085

3085번: 사탕 게임

문제 : 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

 

NxN 크기에 사탕을 넣고(색깔 4개) 색이 다른 인접한 두칸을 골라 서로 사탕을 교환한다.

모두 같은 색으로 이루어진 가장 긴 연속부분(행 or 열)을 골라서 다 먹는데 그 최대 개수를 구하라는 문제이다.

시간 복잡도는 O(N^2)이고 N ≤ 50 이므로 전체 경우의 수가 몇 개 안되니까 브루트 포스를 이용할 수 있다.

 

행을 기준으로 하나를 바꾸고 연속하는 행/열의 최대 개수를 찾고 다시 원상복귀시켜 모든 행을 검사해본다.

마찬가지로 열을 기준으로 하나를 바꾸고 연속하는 행/열의 최대 개수를 찾고 원상복귀 시켜 모든 열을 검사해보고 그중 가장 큰 값을 출력하면 된다!!

#include<iostream>
#include<algorithm>
using namespace std;
char a[51][51];
int ans;
int n;
void check();
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < n; i++) { // 행 바꾸기
		for (int j = 0; j < n - 1; j++) {
			swap(a[i][j], a[i][j + 1]);
			check();
			swap(a[i][j], a[i][j + 1]);
		}
	}
	for (int j = 0; j < n; j++) { // 열 바꾸기
		for (int i = 0; i < n - 1; i++) {
			swap(a[i][j], a[i + 1][j]);
		   	check();
			swap(a[i][j], a[i + 1][j]);
		}
	}
	cout << ans;
}

void check() {
	char c;
	for (int i = 0; i < n; i++) { // 행 계산
		int count = 1; // 1개부터 시작
		c = a[i][0];
		for (int j = 1; j < n; j++) {
			if ((a[i][j] == c)) {
				count += 1;
			}
			else count = 1;
			c = a[i][j];
			if (count > ans) ans = count;
		}
	}

	for (int j = 0; j < n; j++) { // 열 계산
		int count = 1;
		c = a[0][j];
		for (int i = 1; i < n; i++) {
			if ((a[i][j] == c)) {
				count += 1;
			}
			else count = 1;
			c = a[i][j];
			if (count > ans) ans = count;
		}
	}
}