알고리즘 :: 백준 :: Bruteforce :: 3085 :: 사탕 게임

문제

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

문제접근

• 많은 대기업에서 사랑하는 시뮬레이션 기반 bruteforce 유형 문제다. 하나씩 차근차근 접근해보자.
• 문제의 상한값은 알고리즘에 따라 다르다.
  • N2개의 칸 중 임의의 칸을 고른다.
    • 상, 하, 좌, 우로 사탕을 교환한 후 모든 행과 열에 대해 최대 연속 사탕 개수를 구한다 -> $O(N^3)$
    • 오른쪽, 아래로만 사탕을 교환한 후 현재 행(열), 바꾼 행(열)을 검사한다 -> $O(3N^2)$
• 본 문제는 보드의 크기가 50이므로 첫 번째 방법을 사용해도 시간내에 풀이할 수 있다. 그러나 여기서는 두 번째 방법을 사용해서 문제를 풀어보도록 한다.

풀이과정은 다음과 같다.

• 5X5 보드에 위와 같이 사탕이 배열되어있을 때, 우리는 모든 칸을 우측, 아래로 교환할 것이다.
• 먼저 교환을 시작하기 전에, 주어진 보드에 대해 최대 사탕 개수검사를 수행한다. 현재는 3개가 최대다.
• 선택한 현재 칸의 행과 열, 교환한 칸의 행과 열에 대해 연속된 색의 사탕 개수를 검사할 것이다.
  
• 2행 1열에 있는 빨간색 사탕을 선택했다고 가정하자. 그렇다면 오른쪽으로 교환했을 때는 우측 그림이, 아래쪽으로 교환했을 때는 아래 그림이 나올 것이다. 교환을 수행하면 우리는 파란색 선으로 표시된 부분만 다시 검사하면 된다.
• 재검사를 수행했더니 오른쪽 교환시 최대 사탕개수를 4개로 갱신할 수 있음을 확인할 수 있다.

코드

#include <iostream>
using namespace std;

int N;
char board[50][50];

void swap(int& lhs, int& rhs) {
	int temp = lhs;
	lhs = rhs;
	rhs = temp;
}
int checkLines(int y, int x) {
	int retRow = 1, retCol = 1;
	char c = board[y][x];
	for (int i = x + 1; i < N; ++i) {
		if (c == board[y][i]) retRow++;
		else break;
	}
	for (int i = x - 1; i >= 0; --i) {
		if (c == board[y][i]) retRow++;
		else break;
	}
	for (int i = y + 1; y < N; ++i) {
		if (c == board[i][x]) retCol++;
		else break;
	}
	for (int i = y - 1; y >= 0; --i) {
		if (c == board[i][x]) retCol++;
		else break;
	}
	return max(retRow, retCol);
}
int preprocess() {
	int ret = 0;
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < N; ++x) 
			ret = max(ret, checkLines(y, x));
	return ret;
}
int solve() {
	// 모든 칸에 대해 오른쪽, 아래쪽만 비교하고 교환해준다.
	// 교환해준 다음에는 현재 칸, 바꾼 칸에 대해 행과 열을 검사한다.
	int ret = preprocess();
	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < N; ++x) {
			if (x + 1 < N && board[y][x] != board[y][x + 1]) {	// 우측 교환
				swap(board[y][x], board[y][x + 1]);		// 교환해주고, 검사한 뒤,
				ret = max(ret, max(checkLines(y, x), checkLines(y, x + 1)));
				swap(board[y][x], board[y][x + 1]);		// 교환을 해제한다. 
			}
			if (y + 1 < N && board[y][x] != board[y + 1][x]) {	// 하단 교환
				swap(board[y][x], board[y + 1][x]);
				ret = max(ret, max(checkLines(y, x), checkLines(y + 1, x)));
				swap(board[y][x], board[y + 1][x]);
			}
		}
	}
	return ret;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			cin >> board[i][j];
	
	cout << solve() << '\n';
}

결과