[BOJ] 3085 : BOMBONI - travelbeeee

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

---

[ 알고리즘풀이 ]

1. Map에서 가능한 모든 경우에 대해(인접한 곳) 색깔을 바꾼다.

2. 색깔을 바꾼 Map에 대해서 최대 Score를 계산해 답을 갱신한다.

#include<iostream>
#include<algorithm>

using namespace std;
int N, ans = -1;
char map[50][51] = {};

int getScore(char tempMap[50][51]) {
	int m = -1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int score1 = 0, score2 =0;
			for (int k = j; k < N; k++)
				if (tempMap[i][j] == tempMap[i][k])
					score1++;
				else
					break;
			for (int k = i; k < N; k++)
				if (tempMap[i][j] == tempMap[k][j])
					score2++;
				else
					break;
			m = max(m, score1);
			m = max(m, score2);
		}
	}
	return m;
}

void Change(int a, int b, int c, int d) {
	char tempMap[50][51] = {};
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			tempMap[i][j] = map[i][j];
	char temp = tempMap[a][b];
	tempMap[a][b] = tempMap[c][d];
	tempMap[c][d] = temp;
	ans = max(ans, getScore(tempMap));
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> map[i];
	// colChange
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N - 1; j++)
			Change(i, j, i, j + 1);
	for (int j = 0; j < N; j++)
		for (int i = 0; i < N - 1; i++)
			Change(i, j, i + 1, j);
	cout << ans;
	return 0;
}

---