[BOJ] 백준 3085 사탕 게임

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

Approach

완전탐색  유형 문제이다.

완전탐색 기법이란?

 

인접한 2 칸을 선택하고 위치를 서로 교환한다.

(대각선은 인접하지 않으며 세로/가로 방향으로 인접한 것으로 정의)

 

- 최대 N이 크지 않은 수치이기 때문에  (3 ≤ N ≤ 50)

  세로 방향과 가로 방향으로 구분해서 변경할 수 있는 위치를 모두 바꿔(swap)본다.

- 바꿔볼 때마다 먹을 수 있는 사탕 개수를 확인하다.

- 최대로 먹을 수 있는 사탕 개수를 갱신하가며 저장

- 위치 변경하고 다음 Case를 위해서 위치를 원상복구 해준다.

 

구현 순서

① 세로 방향으로 (위치)교환 시도

    - 가로줄로 먹을 수 있는 최대 사탕 개수 확인

    - 세로줄로 먹을 수 있는 최대 사탕 개수 확인

② 가로 방향으로 (위치)교환 시도

    - 가로줄로 먹을 수 있는 최대 사탕 개수 확인

    - 세로줄로 먹을 수 있는 최대 사탕 개수 확인

---

#include <iostream>

using namespace std;
const int MAX_N = 50 + 2;
int n, ans, cnt;
char map[MAX_N][MAX_N];
inline void swap(char &A, char &B) { char tmp = A; A = B; B = tmp; }
inline int max(int A, int B) { return A > B ? A : B; }

void input()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
		}
	}
}

void checkHorizontal()
{
	for (int i = 0; i < n; i++)
	{
		cnt = 1;
		for (int j = 0; j < n; j++)
		{
			if (map[i][j] == map[i][j + 1])
			{
				cnt++;
			}
			else
			{
				ans = max(ans, cnt);
				cnt = 1;
			}
		}
	}
}

void checkVertical()
{
	for (int i = 0; i < n; i++)
	{
		cnt = 1;
		for (int j = 0; j < n; j++)
		{
			if (map[j][i] == map[j + 1][i])
			{
				cnt++;
			}
			else
			{
				ans = max(ans, cnt);
				cnt = 1;
			}
		}
	}
}

int main()
{
	// freopen("input.txt", "r", stdin);
	input();

	// 세로 방향 교환
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1; j++)
		{
			swap(map[i][j], map[i][j + 1]);
			checkVertical();
			checkHorizontal();
			swap(map[i][j], map[i][j + 1]);
		}
	}

	// 가로 방향 교환
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1; j++)
		{
			swap(map[j][i], map[j+1][i]);
			checkVertical();
			checkHorizontal();
			swap(map[j][i], map[j + 1][i]);
		}
	}

	printf("%d\n", ans);
}