[ 백준 BOJ / c++ ] 3085번 사탕게임

🤔 문제

 

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

---

👀 접근 방식

우선 아래와 같이 접근하였다.

1. 사탕교환시 인덱스 범위를 초과하는 것을 막기위해 패딩 1을 더한 크기 52*52의 배열을 만든다.
2. 입력된 각 문자에 대해 상하좌우 각각 이동시 먹을 수 있는 최대 사탕수를 계산한다.
3. 최대가 되는 사탕값을 저장한다.

문제를 처음 보았을때, 사탕이 교환 즉, 배열 값들이 이동하여야하기 때문에 따로 if문을 추가해 예외처리하기 번거로울 것 같아 패딩을 추가하는 것을 먼저 생각하였다. 아래와 같이 패딩을 추가해 교환시에도 인덱스 오류가 발생 위험을 없앴다. 

 

또한, 최대 개수를 검사할때는 패딩을 제외한 영역을 검사하여, 연속된 패딩 값이 최대값이 되는것을 방지하였다.

마지막으로, 연속된 사탕의 최대 개수는 행, 열 각각 계산후 가장 큰 값을 저장하는 방향으로 진행하였다.

 

---

💻 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include<stack>
#include<string>

using namespace std;

char maps[52][52];
int n;
int answer = 1;

void UpdateValue(int y, int x, int mode)
{
	// mode -> 0 : 기본 , 1 : 위 교환, 2 : 아래 교환, 3: 왼쪽 교환, 4 : 오른쪽 교환

	char sub[52][52];

	for (int i = 0; i <= 51; ++i)
	{
		for (int j = 0; j <= 51; ++j)
		{
			sub[i][j] = maps[i][j];
		}
	}

	if (mode == 1)
	{
		// 위
		char tmp = sub[y][x];
		sub[y][x] = sub[y - 1][x];
		sub[y - 1][x] = tmp;
	}
	else if (mode == 2)
	{
		//아래
		char tmp = sub[y][x];
		sub[y][x] = sub[y + 1][x];
		sub[y + 1][x] = tmp;
	}
	else if (mode == 3)
	{
		//왼
		char tmp = sub[y][x];
		sub[y][x] = sub[y][x - 1];
		sub[y][x - 1] = tmp;
	}
	else if (mode == 4)
	{
		//오른
		char tmp = sub[y][x];
		sub[y][x] = sub[y][x + 1];
		sub[y][x + 1] = tmp;
	}

	int _max = 0;


	// 행 개수 찾기
	for (int i = 1; i <= n; ++i)
	{
		int cnt = 0;
		char curC = sub[i][1];

		for (int j = 1; j <= n; ++j)
		{
			if (sub[i][j] == curC)
			{
				cnt++;
			}
			else {
				_max = max(_max, cnt);
				cnt = 1;
				curC = sub[i][j];
			}
		}

		_max = max(_max, cnt);
	}

	// 열 개수 찾기
	for (int i = 1; i <= n; ++i)
	{
		int cnt = 0;
		char curC = sub[1][i];

		for (int j = 1; j <= n; ++j)
		{
			if (sub[j][i] == curC)
			{
				cnt++;
			}
			else {
				_max = max(_max, cnt);
				cnt = 1;
				curC = sub[j][i];
			}
		}

		_max = max(_max, cnt);
	}

	answer = max(_max, answer);
}

int main()
{
	/*
		패딩을 하나 넣은 52*52 배열에 저장
		문장을 n개 입력받아 패딩에는 E를 넣고
		다른 부분에는 C,P,Z,Y를 넣음

		1~50에 대해 상하좌우로 움직일 경우의 사탕의 개수를 구함 -> UpdateValue() 함수 구현
	*/

	// 배열 E로 초기화
	for (int i = 0; i <= 51; ++i)
	{
		for (int j = 0; j <= 51; ++j)
		{
			maps[i][j] = 'E';
		}
	}

	// n 입력
	cin >> n;

	// 문장 입력받아 쪼개기
	for (int i = 1; i <= n; ++i)
	{
		string input; cin >> input;

		for (int j = 1; j <= n; ++j)
		{
			maps[i][j] = input[j - 1];
		}
	}

	// (i, j) 문자에 대해 상하좌우 움직였을때 연속되는 사탕의 개수를 구함 
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			UpdateValue(i, j, 1);
			UpdateValue(i, j, 2);
			UpdateValue(i, j, 3);
			UpdateValue(i, j, 4);
		}
	}

	//출력
	cout << answer;
}