[BOJ] 3085번_사탕 게임_브루트포스

[문제]

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

N을 입력받은 후 NxN 크기에 색이 다른 사탕을 입력받는다. 그리고 인접하면서 서로 다른 색을 가진 사탕을 골라서 서로 자리를 교환한다. 이런식으로 자리를 교환했을 때, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분의 사탕 개수를 구하는 문제이다.

*원래 알고리즘 문제를 해결할 때 함수를 잘 사용하지 않고 main문에 전부 작성하는 편인데, 이 문제처럼 반복실행되는 코드가 많을 경우엔 함수를 쓰는 연습을 해야할 것 같다.

[사용 알고리즘]

브루트포스 알고리즘

[풀이 핵심]

• 인접한 사탕의 자리를 교환하는 시간은 2중 for문이라 O(N^2)이며, 가로 또는 세로의 가장 긴 연속 부분을 찾는 시간도 2중 for문이라 O(N^2)이다. 따라서 O(N^4)의 시간이 걸리는데 N의 최대크기는 50이므로 브루트포스 알고리즘으로 해결할 수 있는 충분한 시간이다.
• 브루트포스 알고리즘 이므로 문제에서 원하는 조건대로 구현하면된다.

  1. NxN 크기에 사탕을 입력받는다.
  2. 배열의 첫번째 칸부터 오른쪽의 사탕과 자리를 바꾸고 가로, 세로의 가장 긴 연속 부분의 최대 사탕 개수를 세어준다. 그 후 다시 사탕을 제자리로 돌려놓는다.
  3. 2번과 비슷하게, 아래쪽의 사탕과 자리를 바꾸고 가로, 세로의 가장 긴 연속 부분의 최대 사탕 개수를 세어준다. 그 후 다시 사탕을 제자리로 돌려놓는다.
  4. 모든 연산이 끝난후 2번, 3번에서 갱신해왔던 최대 사탕 개수가 답이다.

[코드]

//boj3085번_사탕 게임_브루트포스

#include<iostream>

using namespace std;

char arr[51][51];

int N;
int result = 0;

void check_width() {
	for (int x = 0; x < N; x++) {
		int width = 1;
		for (int y = 0; y < N - 1; y++) {
			if (arr[x][y] == arr[x][y + 1]) {
				width++;
			}
			else {
				result = max(result, width);
				width = 1;
			}
		}
		result = max(result, width);
	}
}

void check_height() {
	for (int x = 0; x < N; x++) {
		int height = 1;
		for (int y = 0; y < N - 1; y++) {
			if (arr[y][x] == arr[y + 1][x]) {
				height++;
			}
			else {
				result = max(result, height);
				height = 1;
			}
		}
		result = max(result, height);
	}
}

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N - 1; j++) {
			swap(arr[i][j], arr[i][j + 1]);

			check_width();
			check_height();

			swap(arr[i][j], arr[i][j + 1]);

			swap(arr[j][i], arr[j + 1][i]);

			check_width();
			check_height();

			swap(arr[j][i], arr[j + 1][i]);
		}
	}
	cout << result;

	return 0;
}