[Baekjoon/C++] 3085번 - 사탕 게임

[백준] Baekjoon Online Judge

문제로 이동

 

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

 

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

 

---

예제 입력	예제 출력
3 CCP CCP PPC	3
4 PPPP CYZY CCPY PPCC	4
5 YCPZY CYZZP CCPPP YCYZC CPPZZ	4

---

풀이

#include <iostream>
#include <algorithm>
using namespace std; 

int N;
char candy[50][50];

int checkGaro(int n);
int checkSero(int n);

// 행에서 연속적인 사탕 개수 체크
int checkGaro(int n) {
	int result = 0, cnt = 1;
	char c = candy[n][0];

	for (int i = 1; i < N; i++) {
		if (candy[n][i] == c) cnt++;
		else {
			c = candy[n][i];
			result = max(result, cnt);
			cnt = 1;
		}
	}

	return max(result, cnt);
}

// 열에서 연속적인 사탕 개수 체크
int checkSero(int n) {
	int result = 0, cnt = 1;
	char c = candy[0][n];

	for (int i = 1; i < N; i++) {
		if (candy[i][n] == c) cnt++;
		else {
			c = candy[i][n];
			result = max(result, cnt);
			cnt = 1;
		}
	}

	return max(result, cnt);
}

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

	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) cin >> candy[i][j];

	int result = 0;

	// 행에서 교환
	for (int i = 0; i < N; i++) {
		if (result == N) break;

		for (int j = 0; j < N - 1; j++) {
			swap(candy[i][j], candy[i][j + 1]);
			result = max(result, checkGaro(i));
			result = max(result, max(checkSero(j), checkSero(j + 1)));
			swap(candy[i][j], candy[i][j + 1]);
		}
	}

	// 열에서 교환
	for (int i = 0; i < N; i++) {
		if (result == N) break;

		for (int j = 0; j < N - 1; j++) {
			swap(candy[j][i], candy[j + 1][i]);
			result = max(result, checkSero(i));
			result = max(result, max(checkGaro(j), checkGaro(j + 1)));
			swap(candy[j][i], candy[j + 1][i]);
		}
	}

	cout << result << '\n';
}

 

	int result = 0;

	// 행에서 교환
	for (int i = 0; i < N; i++) {
		if (result == N) break;

		for (int j = 0; j < N - 1; j++) {
			swap(candy[i][j], candy[i][j + 1]);
			result = max(result, checkGaro(i));
			result = max(result, max(checkSero(j), checkSero(j + 1)));
			swap(candy[i][j], candy[i][j + 1]);
		}
	}

	// 열에서 교환
	for (int i = 0; i < N; i++) {
		if (result == N) break;

		for (int j = 0; j < N - 1; j++) {
			swap(candy[j][i], candy[j + 1][i]);
			result = max(result, checkSero(i));
			result = max(result, max(checkGaro(j), checkGaro(j + 1)));
			swap(candy[j][i], candy[j + 1][i]);
		}
	}

행/ 열에서 인접한 두 사탕의 위치 교환이 일어나는 코드이다. result에 위치 교환이 일어났을 때 먹을 수 있는 최대 사탕의 수가 저장되는 데, 이 result의 값이 N과 같아진다면 더이상 교환을 할 필요성이 없어지기에 if문으로 체크하도록 했다.

 

// 행에서 연속적인 사탕 개수 체크
int checkGaro(int n) {
	int result = 0, cnt = 1;
	char c = candy[n][0];

	for (int i = 1; i < N; i++) {
		if (candy[n][i] == c) cnt++;
		else {
			c = candy[n][i];
			result = max(result, cnt);
			cnt = 1;
		}
	}

	return max(result, cnt);
}

// 열에서 연속적인 사탕 개수 체크
int checkSero(int n) {
	int result = 0, cnt = 1;
	char c = candy[0][n];

	for (int i = 1; i < N; i++) {
		if (candy[i][n] == c) cnt++;
		else {
			c = candy[i][n];
			result = max(result, cnt);
			cnt = 1;
		}
	}

	return max(result, cnt);
}

교환이 발생하고 나면 위의 함수들을 호출하게 된다. 교환이 발생한 사탕의 위치를 포함한 행과 열에만 변화가 생기기에 전체 배열을 확인하는 것은 비효율적이라고 생각했기에 원하는 행/열만 확인할 수 있는 함수를 구현했다.