[BOJ 3085] 사탕 게임

문제 출처

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

3085번: 사탕 게임

 

문제 풀이

모든 경우의 수를 다 탐색하는 문제다. 위치마다 4방향 탐색을 해도 되지만 위쪽과 왼쪽은 조금만 생각해보면 중복되는 처리임을 알 수 있다.

시간 복잡도는 사탕의 위치를 바꾸는 데 2방향(오른쪽, 아래)과 n의 크기로 구하는데 2 X 50 X 50 , 최대 개수를 구하는데는 50 X 50이다. 따라서 2 X 50^4 = 12,500,000으로 1초 안에 풀이가 가능하다.

즉 O(N^4)의 시간 복잡도를 가진 이 알고리즘은 N이 50이하로 작게 제한되어 있기 때문에 완전 탐색을 해도 충분히 풀이할 수 있다고 판단했다.

 

소스 코드

https://github.com/sw93/algorithm/blob/master/BOJ_PS/BOJ_3085/boj3085.cpp

sw93/algorithm

 

#include <iostream>
#include <algorithm>
using namespace std;
int n;
char map[50][50];
void init() {
	cin >> n;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> map[y][x];
		}
	}
}
int eatCandy() {
	int ret = 1;

	// 열 체크
	for (int y = 0; y < n; y++) {
		int count = 1;
		for (int x = 1; x < n; x++) {
			if (map[y][x] == map[y][x - 1]) count++;
			else count = 1;
			ret = max(count, ret);
		}
	}

	// 행 체크
	for (int x = 0; x < n; x++) {
		int count = 1;
		for (int y = 1; y < n; y++) {
			if (map[y][x] == map[y - 1][x]) count++;
			else count = 1;
			ret = max(count, ret);
		}
	}

	return ret;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	init();
	int ans = 0;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {

			// 오른쪽 탐색
			if (x + 1 < n) {
				swap(map[y][x], map[y][x + 1]);
				ans = max(ans, eatCandy());
				swap(map[y][x], map[y][x + 1]);
			}

			// 아래쪽 탐색
			if (y + 1 < n) {
				swap(map[y][x], map[y + 1][x]);
				ans = max(ans, eatCandy());
				swap(map[y][x], map[y + 1][x]);
			}
		}
	}
	cout << ans;
	return 0;
}