[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 사탕 게임 (3085)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 사탕 게임 (3085)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 사탕 게임 (3085)

 

---

 

3085번: 사탕 게임

[ 문제 ]

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

[ 입력 ]

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

[ 출력 ]

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

---

[ 코드 ]

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

// 오른쪽 혹은 아래쪽으로 자리가 변환된 경우, a의 연속값 구하기 위한 함수
int check(vector <string>& a) { // vector<string>값을 인자로 받기
	int n = a.size();
	int ans = 1;

	for (int i = 0; i < n; i++) 
	{
		int cnt = 1;
		for (int j = 1; j < n; j++) // i행
		{
			if (a[i][j] == a[i][j-1]) // i열 : j행이 j-1행과 같은 값이라면
			{
				cnt += 1;
			}
			else // 다른 값이라면
			{
				cnt = 1;
			}

			if (ans < cnt) // ans(기존 연속 값) < cnt(새로 구한 연속 값)라면
				// 즉 가장 긴 값 (먹을 수 있는 같은 종류 사탕의 최대 개수) 저장
			{
				ans = cnt;
			}
		}

		cnt = 1;
		for (int j = 1; j < n; j++) // i열
		{
			if (a[j][i] == a[j-1][i]) // j행 : i열이 i-1열과 같은 값이라면
			{
				cnt += 1;
			}
			else // 다른 값이라면
			{
				cnt = 1;
			}

			if (ans < cnt) // ans(기존 연속 값) < cnt(새로 구한 연속 값)라면
				// 즉 가장 긴 값 (먹을 수 있는 같은 종류 사탕의 최대 개수) 저장
			{
				ans = cnt;
			}
		}

	}
	
	return ans; // 가장 긴 값 반환
}


int main() {
	int N; // 보드의 크기 N*N
	cin >> N;

	vector <string> a(N); // 사탕의 색상 (한 줄에 N개)

	for (int i = 0; i < N; i++)
	{
		cin >> a[i]; // i행 (가로)
	}

	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (j + 1 < N) // 오른쪽 (N-1이 마지막 칸이므로, j+1은 N보다 작아야함)
			{
				swap(a[i][j], a[i][j + 1]); // 같은 i행에, j를 오른쪽과 바꾸기
				int temp = check(a); // 변환된 경우 가장 긴 값 저장 (비교를 위한 임시변수)
				if (ans < temp) // 기존에 있던 값보다 크다면 저장.
				{
					ans = temp;
				}
				swap(a[i][j], a[i][j + 1]); // 다시 원상복귀
			}
			if (i + 1 < N) // 아래
			{
				swap(a[i][j], a[i+1][j]);
				int temp = check(a);
				if (ans < temp)
				{
					ans = temp;
				}
				swap(a[i][j], a[i + 1][j]);
			}
		}
	}

	cout << ans << '\n';
	return 0;
}