BOJ 3085 사탕 게임

문제 링크

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

알고리즘 유형

브루트 포스

시간복잡도

브루트 포스의 시간 복잡도는 \(O(경우의\ 수\times 각\ 경우의\ 시간\ 복잡도)\)

경우의 수

가장 처음에 N×N크기에 사탕을 채워 놓는다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다.

N X N의 각 칸에 대해서 인접한 칸과 swap
칸은 N X N개 X 각 칸의 인접한 칸은 4개 X 인접한 칸마다 swap 1회

\[O(N^2 \times 4 \times 1) = O(N^2)\]

각 경우의 시간복잡도

이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

가장 길게 연속하는 색상은 다음과 같이 찾는다.

연속하는 칸은 행 방향 또는 열 방향으로 존재 가능, 각 행/열에 속한 모든 칸의 색상 검사
총 N개의 행 존재 X 행 마다 N개의 칸 검사 + 총 N개의 열 존재 X 열 마다 N개의 칸 검사

\[O(N \times N + N \times N) = O(N^2)\]

총 시간복잡도

본 문제의 총 시간복잡도는 \(O(N^2 + N^2) = O(N^2)\)

알고리즘 팁

가장 긴 연속 값 찾기

1. 이전 타일 색상을 저장해놓고 현재 타일과 비교
2. 선택한 타일의 색상과 다음 타일의 색상이 동일한지 검사

1번은 ‘이전 타일 색상’을 나타내는 변수를 추가해야하기 때문에 2번 채택

소스코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int N;
string brd[50];
int ans;

// 행 방향 가장 긴 연속 값 검사
void eat_row(int y){
	int clr_ctr;
	
	clr_ctr = 1;
	for (int x = 1; x < N; ++x) {
		if (brd[y][x - 1] == brd[y][x]) {
			++clr_ctr;
			ans = max(ans, clr_ctr);
		}
		else {
			clr_ctr = 1;
		}
	}
}

// 열 방향 가장 긴 연속 값 검사
void eat_col(int x){
	int clr_ctr;

	clr_ctr = 1;
	for (int y = 1; y < N; ++y) {
		if (brd[y - 1][x] == brd[y][x]) {
			++clr_ctr;
			ans = max(ans, clr_ctr);
		}
		else {
			clr_ctr = 1;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> brd[i];
	}

	// row 방향 swap
	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < N - 1; ++x) {
			swap(brd[y][x], brd[y][x + 1]);
			eat_row(y);
			eat_col(x);
			eat_col(x + 1);
			swap(brd[y][x], brd[y][x + 1]);
		}
	}

	// col 방향 swap
	for (int y = 0; y < N - 1; ++y) {
		for (int x = 0; x < N; ++x) {
			swap(brd[y][x], brd[y + 1][x]);
			eat_row(y);
			eat_row(y + 1);
			eat_col(x);
			swap(brd[y][x], brd[y + 1][x]);
		}
	}

	cout << ans;

	return 0;
}