[3085번] 사탕 게임

 

www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

애니팡, 캔디 크러쉬 등의 퍼즐 알고리즘과 비슷한 문제입니다.

 

우선 블록이 이동(교환)할 수 있는 범위를 알아보겠습니다.

 

 

가장자리가 아닌 블록들은 4가지 방향(상, 하, 좌, 우)으로 교환될 수 있습니다.

 

 

모서리를 제외한 가장자리 블록들은 3가지 방향으로 교환될 수 있습니다.

 

 

모서리 블록들은 2가지 방향으로 교환될 수 있습니다.

 

위 조건을 지키면서 모든 블록을 교환하고,

점수를 계산한 뒤 최대 캔디 개수를 구하면 됩니다.

 

저 같은 경우에는 row, col 값을 넣으면 해당 블록을 중심으로

상하, 좌우에 연속된 같은 캔디 개수를 세는 함수를 따로 만들었습니다.

 

// (row, col)을 기준으로 최대 캔디를 계산
void candyCheck(int row, int col)
{
	int up, down;
	up = 1;
	down = 1;

	// 상, 하 캔디 개수의 총합
	int sum;
	sum = 1;

	// 상
	if (row > 0)
	{
    		// 다른 캔디가 나올 때까지 반복하면서 캔디 개수 증가(+ 1)
		while (board[row][col] == board[row - up][col])
		{
			sum += 1;
			up += 1;

			if (row - up < 0)
			{
				break;
			}
		}
	}

	// 하
	if (row < N - 1)
	{
        	// 다른 캔디가 나올 때까지 반복하면서 캔디 개수 증가(+ 1)
		while (board[row][col] == board[row + down][col])
		{
			sum += 1;
			down += 1;

			if (row + down > N - 1)
			{
				break;
			}
		}
	}

	// maxCandy(전역변수): 현재까지 최대 캔디 개수
    	// 현재 구한 캔디 값(sum)이 maxCandy보다 많다면 값 변경
	if (maxCandy < sum)
	{
		maxCandy = sum;
	}

	int left, right;
	left = 1;
	right = 1;

	// 좌, 우 캔디 개수의 총합
	sum = 1;

	// 좌
	if (col > 0)
	{
    		// 다른 캔디가 나올 때까지 반복하면서 캔디 개수 증가(+ 1)
		while (board[row][col] == board[row][col - left])
		{
			sum += 1;
			left += 1;

			if (col - left < 0)
			{
				break;
			}
		}
	}

	// 우
	if (col < N - 1)
	{
    		// 다른 캔디가 나올 때까지 반복하면서 캔디 개수 증가(+ 1)
		while (board[row][col] == board[row][col + right])
		{
			sum += 1;
			right += 1;

			if (col + right > N - 1)
			{
				break;
			}
		}
	}

	if (maxCandy < sum)
	{
		maxCandy = sum;
	}
}

 

위 함수를 이용하면 특정 블록을 이동했을때,

최대로 얻을 수 있는 캔디의 개수를 구할 수 있으므로

 

이제 반복문을 사용하여 모든 블록에 함수를 적용해주기만 하면 됩니다.

 

#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

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

int N;
char board[51][51];
int maxCandy;

void candyCheck(int row, int col)
{
	int up, down;
	up = 1;
	down = 1;

	int sum;
	sum = 1;

	// 상
	if (row > 0)
	{
		while (board[row][col] == board[row - up][col])
		{
			sum += 1;
			up += 1;

			if (row - up < 0)
			{
				break;
			}
		}
	}

	// 하
	if (row < N - 1)
	{
		while (board[row][col] == board[row + down][col])
		{
			sum += 1;
			down += 1;

			if (row + down > N - 1)
			{
				break;
			}
		}
	}

	if (maxCandy < sum)
	{
		maxCandy = sum;
	}

	int left, right;
	left = 1;
	right = 1;

	sum = 1;

	// 좌
	if (col > 0)
	{
		while (board[row][col] == board[row][col - left])
		{
			sum += 1;
			left += 1;

			if (col - left < 0)
			{
				break;
			}
		}
	}

	// 우
	if (col < N - 1)
	{
		while (board[row][col] == board[row][col + right])
		{
			sum += 1;
			right += 1;

			if (col + right > N - 1)
			{
				break;
			}
		}
	}

	if (maxCandy < sum)
	{
		maxCandy = sum;
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N;

	maxCandy = 0;

	for (int i = 0; i < N; i++)
	{
		string row;
		cin >> row;

		for (int j = 0; j < N; j++)
		{
			board[i][j] = row[j];
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			char ca;

			// 상
			if (i > 0)
			{
				ca = board[i][j];
				board[i][j] = board[i - 1][j];
				board[i - 1][j] = ca;

				candyCheck(i - 1, j);

				board[i - 1][j] = board[i][j];
				board[i][j] = ca;
			}

			// 하
			if (i < N - 1)
			{
				ca = board[i][j];
				board[i][j] = board[i + 1][j];
				board[i + 1][j] = ca;

				candyCheck(i + 1, j);

				board[i + 1][j] = board[i][j];
				board[i][j] = ca;
			}

			// 좌
			if (j > 0)
			{
				ca = board[i][j];
				board[i][j] = board[i][j - 1];
				board[i][j - 1] = ca;

				candyCheck(i, j - 1);

				board[i][j - 1] = board[i][j];
				board[i][j] = ca;
			}

			// 우
			if (j < N - 1)
			{
				ca = board[i][j];
				board[i][j] = board[i][j + 1];
				board[i][j + 1] = ca;

				candyCheck(i, j + 1);

				board[i][j + 1] = board[i][j];
				board[i][j] = ca;
			}
		}
	}

	printf("%d\n", maxCandy);

	return 0;
}