#3085: 사탕 게임

백준 3085번: 사탕 게임

문제:

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

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

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

입력:

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

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

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

풀이:

• 이 문제는 난이도는 어렵지 않지만 구현 하는데 상당히 오랜 시간이 걸린다. 우선 4중 for문을 쓸 거라고 생각을 못 했기 때문에 효율적인 방법을 생각하다가 시간을 너무 많이 사용한 것 같다. n의 최대값이 50이여서 4중 for문을 써도 경우의 수가 엄청 커지지는 않아서 그런 것이다.
• 이 문제를 푸는 방법은 여러가지 방법이 있지만 제일 중요한 핵심은 브루트 포스 알고리즘에 알맞게 모든 칸을 다 바꿔본 뒤에 최대 길이를 저장한 뒤 출력 하는 것이다. 우선 2중 for문으로 배열의 모든 값을 다 방문 해준 뒤 아래 오른쪽의 값이 다른 경우 뒤집어 볼 것이다.
• 뒤집은 후에는 길이를 제어 주어야 되는데 길이를 젤 때는 현재 값과 다른 경우가 나올 때가지 아래/오른쪽과 위/왼쪽을 모두 확인 해주어야 된다. 확인이 끝나면 최대값을 기록해주며 카운터를 다시 1로 돌려준다. 그것을 구현한 것이 count_horizontal_max와 count_vertical_max 함수이다. 배열을 바꾼 뒤에는 원래 배열로 돌아와야 하니 initialize_board()를 이용하여 원래 보드 값을 temp 배열에 다시 복사해 준다.
• 값을 바꾼 뒤 확인할 때는 현재 배열의 값의 줄도 세로 및 가로로 확인 해주어야 되지만 바꾼 값이 영향을 주는 줄도 길이를 확인해주어야 된다. 예를 들면, 아래 값과 바꿀 경우 아래 바뀐 값의 가로 줄의 최대길이도 확인 해주어야 된다. 또한, 바꾸는 경우만 고려하는 것이 아닌 아무 것도 안바꾸었을 경우도 고려해야 된다.

코드:

#include <iostream>

using namespace std;

int n, counter = 1, answer=0;
char board[51][51]={}, temp[51][51]={};

//입력 받은 board 배열 값들 temp에 복사
void initialize_board(){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++) temp[i][j] = board[i][j];
	}
}
//현재 자리와 같은 연속 된 가로 값들을 찾음
void count_horizontal_max(int row, int col){
	//오른쪽에 같은 값이 있는 경우
	for(int k = col+1; k <= n; k++){
		//다른 값이 나오는 경우 바로 for문 탈출
		if(temp[row][col]!=temp[row][k]) break;
		counter++;
	}
	//왼쪽으로 같은 값이 있는 경우
	for(int k = col-1; k > 0; k--){
		//다른 값이 나오는 경우 바로 for문 탈출
		if(temp[row][col]!=temp[row][k]) break;
		counter++;
	}
	answer = max(answer,counter);
	counter = 1;
}
//현재 자리와 같은 연속 된 세로 값들을 찾음
void count_vertical_max(int row, int col) {
	//아래로 같은 값이 있는 경우
	for(int k = row+1; k <= n; k++){
		//다른 값이 나오는 경우 바로 for문 탈출
		if(temp[row][col]!=temp[k][col])break;
		counter++;
	}
	//위로 같은 값이 있는 경우
	for(int k = row-1; k > 0; k--){
		//다른 값이 나오는 경우 바로 for문 탈출
		if(temp[row][col]!=temp[k][col]) break;
		counter++;
	}
	answer = max(answer,counter);
	counter = 1;
}

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++) cin >> board[i][j];
	}
	initialize_board();
	//1부터 n까지 좌우 위아래 모든 값을 다 바꿔서 확인 해봄
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			//아래값이 존재하고 다를 경우 바꿈
			if(board[i][j]!=board[i+1][j] && i+1<=n){
				//배열 값 변환
				char swap = temp[i][j];
				temp[i][j] = temp[i+1][j];
				temp[i+1][j] = swap;
				count_horizontal_max(i, j); //현재 확인 중인 값의 가로 최대 길이 확인
				count_horizontal_max(i+1, j); //아래줄도 바뀌었으니 가로 최대 길이 확인
				count_vertical_max(i,j); //세로로 값을 바꾸었으니 현재 확인 중인 값의 세로 최대 길이 확인
			}
			initialize_board(); //배열 값 변환하였으니 보드 초기화
			//오른쪽 값이 존재하고 다를 경우 바꿈
			if(board[i][j]!=board[i][j+1] && j+1<=n){
				//배열 값 변환
				char swap = temp[i][j];
				temp[i][j] = temp[i][j+1];
				temp[i][j+1] = swap;
				count_vertical_max(i,j); //현재 확인 중인 값의 세로 최대 길이 확인
				count_vertical_max(i,j+1); //오른쪽 줄도 바뀌었으니 세로 최대 길이 확인
				count_horizontal_max(i,j); //가로로 값을 바꾸었으니 현재 확인 중인 값의 가로 최대 길이 확인
			}
			initialize_board(); //배열 값 변환하였으니 보드 초기화
			count_horizontal_max(i, j); //배열 값을 변환 안하였을 때 가로 최대 길이 확인
			count_vertical_max(i,j); //배열 값을 변환 안하였을 때 세로 최대 길이 확인
		}
	}
	//출력
	cout<<answer;
}