[백준 3085 c++] 사탕 게임

문제 링크

www.acmicpc.net/problem/3085

3085번: 사탕 게임

문제 접근

// 접근 사탕을 인접을 어떻게 바꾸는지 의미가 애매해서 헤멧지만 가로와 세로끼리만 바꾼다

 

 

 

 

 

 

문제 풀이

// 풀이: 완전탐색으로 가로,세로 교환할 때 각 사탕의 최대개수 중 큰 수를 출력

 

 

 

 

 

 

 

 

주의

 

 

 

 

개념

// 개념: swap(board[i][j], board[i][j+1]); string 객체의 원소를 바꿀 수 있다

 

 

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio> // c 문법 헤더파일
#include<string> // c++ 문자열 클래스
#include<vector> // 동적배열 라이브러리
#include<stack>
#include<queue>
#include<algorithm>  // sort와 unique 사용
#include<cmath> // 제곱이나 루트함수 사용
#include<cstring> // memset 함수
#include <set>
#include <map> // map구조체
#include <numeric> //accumulate(v.begin(), v.end(), 0);

// [백준 3085 c++] 사탕 게임
// 접근 사탕을 인접을 어떻게 바꾸는지 의미가 애매해서 헤멧지만 가로와 세로끼리만 바꾼다
// 풀이: 완전탐색으로 가로,세로 교환할 때 각 사탕의 최대개수 중 큰 수를 출력
// 개념: swap(board[i][j], board[i][j+1]); string 객체의 원소를 바꿀 수 있다

using namespace std; // cin,cout 편하게 사용 라이브러리

#define MAX 50
int n;
string board[MAX];

int numofcandy()
{
	// 가로 최대 사탕
	int Max = 0;
	for (int i = 0; i < n; i++)
	{
		int c1 = 0;
		int c2 = 0;
		for (int j = 0; j < n-1; j++)
		{
			// 가로 사탕 최대 검사
			if (board[i][j] == board[i][j + 1])
			{
				c1++;
				if (c1 > Max)
				{
					Max = c1;
				}
			}
			else { c1 = 0; }
			// 세로 사탕 최대 검사
			if (board[j][i] == board[j+1][i])
			{
				c2++;
				if (c2 > Max)
				{
					Max = c2;
				}
			}
			else { c2 = 0; }
			
		}
	}
	return Max;
}

int main()
{
	// IO 속도 향상
	//ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		cin >> board[i];
	}
	// 완전 탐색
	int maxcandy = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n-1; j++)
		{
			// 가로 교환
			swap(board[i][j], board[i][j+1]);
			maxcandy = max(maxcandy, numofcandy());
			swap(board[i][j ], board[i][j+1]);

			// 세로 교환
			swap(board[j][i], board[j + 1][i]);
			maxcandy = max(maxcandy, numofcandy());
			swap(board[j][i], board[j + 1][i]);
		}
	}
	cout << maxcandy+1 << '\n';
	

	return 0;
}