[완전 탐색] 백준 문제 풀이 - 3085 사탕 게임

👩🏻‍💻 문제링크

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

3085번: 사탕 게임

 

✍️ 아이디어

1. 문제 이해

• 문제를 처음에 이해하지 못해서 그냥 강의를 들었다
• 문제는 n x n 크기에 여러 색의 사탕을 놓고 인접한 곳의 사탕의 색이 다르면 둘을 바꿔서 전체에서 사탕 색이 몇개나 연속되는지 구한다 

2. 배열에서 최대 몇개까지 연속되는지 찾게 해주는 함수를 만듬

3. 로직

1. 사탕 색이 가로로or세로로 다른 사탕들을 바꾼다
2. 사탕이 같은 색깔로 최대 몇개까지 연속으로 나오는지 구한다
3. 바꿨던 사탕들을 원위치 시킨다

 

✍️소스코드

• 구현하는데에 애먹음

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int ans=0;
int n;
int max_ans(vector <string> &vv) // 바꾼 new 배열은 최대 몇개가 연속 되는지 찾음
{
	int max=1;
	for(int i=0; i<n; i++)
	{
		int max1=1;
		for(int j=0; j<n; j++)
		{
			if(vv[i][j] == vv[i][j+1])
				max1++;
			else max1=1; //이거 안하면 zzzcyyy 상황에서 6 나오게 함
			if(max<max1)
				max=max1;
		}
	}
	for(int i=0; i<n; i++)
	{
		int max2=1;
		for(int j=0; j<n; j++)
		{
			if(vv[j][i] == vv[j+1][i])
				max2++;
			else max2=1;
			if(max<max2)
				max=max2;
		}
	}
	return max;
}

int main()
{
	cin>>n;
	vector <string> v(n+1);
	for(int i=0; i<n; i++)
	{
		cin>>v[i];
	}
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{
			if(v[i][j] != v[i][j+1]) //사탕색깔이 가로로 다르면
			{
				swap(v[i][j],v[i][j+1]);//가로의 사탕을 바꾸고
				int tmp=max_ans(v);//연속하는 최대수를 구함
				if(ans<tmp)
				   ans=tmp;
				swap(v[i][j],v[i][j+1]);//최대수 구하고 다시 사탕 원위치
			}
			if(v[i][j] != v[i+1][j])//사탕색깔이 세로로 다르면
			{
				swap(v[i][j],v[i+1][j]);
				int tmp2=max_ans(v);
				if(ans<tmp2)
				   ans=tmp2;
				swap(v[i][j],v[i+1][j]);
			}
		}
	}
	cout<<ans<<'\n';
}

(다른 사람 코드도 내꺼랑 로직이 같다)

 

체감난이도	걸린시간	참고	사용 문법
상(문제 이해가 힘들었음)	1hour	강의 참고	완전 탐색(그냥 다 해보기)