[백준 BOJ][C++]3085번 사탕 게임 풀이: 브루트 포스

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

3085번: 사탕 게임

 

 이 문제는 브루트 포스 알고리즘을 사용하여 해결하는 문제입니다. 

 

 브루트 포스 알고리즘은 가능한 모든 경우를 확인하여 결과를 도출해내는 알고리즘입니다. 

 

 보드에서 교환할 수 있는 사탕은 위, 아래, 왼쪽, 오른쪽입니다.

 

 우리는 보드에서 어느 한 사탕의 위치 (x, y)에서 교환하기 전의 가장 긴 부분과 교환한 후의 가장 긴 부분을 비교하여 더 긴 길이를 얻으면 됩니다! 이 과정을 모든 위치에 대해 반복하면 문제를 해결할 수 있습니다. 

 

[풀이 과정]

1. 보드의 위치 (x, y)에서 x열과 y행에 대해 가장 긴 길이를 얻는다.

2. (x, y)에서 위, 아래, 왼쪽, 오른쪽 중 교환할 수 있는 위치와 교환하여 가장 긴 길이를 얻는다.

3. 가장 긴 길이를 결과에 저장한다.

4. 보드의 모든 위치를 검사할 때까지 1~3의 과정을 수행한다. 

 

index	0	1	2
0	C	C	P
1	C	C	P
2	P	P	C

 

 다음 보드에서 (2, 2)를 기준으로 교환하기 전 최대 길이를 볼까요?

index	0	1	2
0	C	C	P
1	C	C	P
2	P	P	C

 2열과 2행을 각각 탐색하면 최대 길이는 2가 되겠네요.

 

 이제 교환 후 최대 길이를 봅시다. 

 

 (2, 2) 에서 교환할 수 있는 위치는 위, 왼쪽입니다. 먼저 위쪽으로 교환하겠습니다. 

 

index	0	1	2
0	C	C	P
1	C	C	C
2	P	P	P

 

 (2, 2) 위치의 문자가 C -> P로 바꼈죠! 이때 최대 길이는 3입니다. 

 

 왼쪽으로도 교환해보겠습니다. 

 

index	0	1	2
0	C	C	P
1	C	C	P
2	P	C	P

 역시 최대길이는 3이 되네요.

 

이 과정을 보드의 모든 위치에 대해 수행하면 결과를 얻을 수 있습니다. 

 

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<algorithm>

using namespace std;

int n;
char map[51][51];

void swap(char& a, char& b) {
	char temp;

	temp = a;
	a = b;
	b = temp;
}

int length(int x, int y) {
	int xans = 0, yans = 0;
	int len = 1;
	char xc, yc;

	xc = map[y][0];
	for (int i = 1; i < n; i++) { //y행에서 최대 길이
		if (xc == map[y][i]) {
			len++;
		}
		else {
			xc = map[y][i];
			len = 1;
		}
		xans = max(xans, len);
	}
	len = 1;
	yc = map[0][x];
	for (int i = 1; i < n; i++) { //x열에서 최대 길이 
		if (yc == map[i][x]) {
			len++;
		}
		else {
			yc = map[i][x];
			len = 1;
		}
		yans = max(yans, len);
	}

	return max(xans, yans);
}

int main(void) {

	int ans = 0;

	cin >> n;

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

	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; j++) {
			ans = max(ans, length(j, i)); //교환하기 전 i행과 j열에서의 최대 길이
			for (int k = 0; k < 4; k++) {
            	//교환할 문자의 위치 위, 아래, 왼쪽, 오른쪽
				int tx = j + dx[k];
				int ty = i + dy[k];

				if (tx < 0 || tx >= n || ty < 0 || ty >= n)
					continue;
				if (map[i][j] == map[ty][tx])
					continue;

				swap(map[i][j], map[ty][tx]); //교환
				int ret = length(j, i);
				ans = max(ans, ret);
				swap(map[i][j], map[ty][tx]); //원래대로
			}

			if (ans == n) {
				cout << ans;
				return 0;
			}
		}
	}

	cout << ans;

	return 0;
}