[백준] 3085번 - 사탕게임

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

3085번: 사탕 게임

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

char **board;
int boardSize;

void init()
{
	string str;
	cin >> boardSize;
	board = new char*[boardSize];
	for(int i=0; i< boardSize; i++)
		board[i] = new char[boardSize];
		
	for(int i=0; i<boardSize; i++)
	{
		cin >> str;
		for(int j=0; j<boardSize; j++)
		{
			board[i][j]=str.at(j);
		}
	}	
}


int getMaximum()
{
	int maximum = 0,temp_max,count;
	
	//가로 확인
	for(int i=0; i<boardSize; i++)
	{
		temp_max = 1;
		count = 1;
		for(int j=0; j<boardSize-1; j++)
		{
			if(board[i][j] == board[i][j+1])
			{
				count++;
				if(temp_max < count)
					temp_max = count;
			}
			else
			{
				count = 1;
			}
			if(maximum < temp_max)
				maximum = temp_max;
		}
	}
	
	//세로 확인
	for(int i=0; i<boardSize; i++)
	{
		temp_max = 1;
		count = 1;
		for(int j=0; j<boardSize-1; j++)
		{
			if(board[j][i] == board[j+1][i])
			{
				count++;
				if(temp_max < count)
					temp_max = count;
			}
			else
			{
				count = 1;
			}
			if(maximum < temp_max)
				maximum = temp_max;
		}
	}
	
	return maximum;
}


void swap(int x1,int y1,int x2, int y2 )
{
	char temp = board[x1][y1];
	board[x1][y1] = board[x2][y2];
	board[x2][y2] = temp;
}



int main() {
	init();
	
	int maximum=0;
	int result;
	
	for(int i=0; i<boardSize; i++)
	{
		for(int j=0; j<boardSize-1; j++)
		{
			swap(i,j,i,j+1);
			result = getMaximum();
			if(result > maximum)
				maximum = result;
			swap(i,j,i,j+1);
			
			swap(j,i,j+1,i);
			result = getMaximum();
			if(result > maximum)
				maximum = result;
			swap(j,i,j+1,i);
		}
	}
	cout << maximum; 
	return 0;
}

문제는 흔히 애니팡과 같은 게임에서 볼 수 있는 경우이다. 오직 2개의 연속된 사탕을 1번만 교환해서 얻을수 있는 가장 긴 사탕의 길이를 구하는 문제인데, 보드의 크기가 최대 50개임을 고려하여 모든 경우의 수를 고려해보기로 하였다.

 

 

문제를 해결하기 위해 구현한 코드중 핵심적인 부분은 getMaximum 함수와 main의 for문이다.

 

getMaximum 함수의 경우, 2개의 큰 for문을 통해 board에 가로부분 최댓값, 세로부분 최댓값을 각각 확인해 줄 수 있도록 하였다. for문은 board의 현재지점과 그 다음지점을 비교하여 같다면 count 를 늘려주고, 다르다면 count를 0으로 바꿔주는 방식으로 구현하였고 각각의 지점에서의 count 값을 매번 임시 최댓값과 비교해줌으로써 최댓값을 최신화해주었다.

가로줄의 최댓값을 찾을 때 위와 같은 방식으로 for문을 돌리다보니 j 루프의 조건을 j < boardSize -1 로 해주어야 null을 참조하는 문제가 일어나지 않았고, 세로줄을 할때 동일하게 조건을 한 뒤 참조할때 j 와 i 위치를 바꿔주면서 최대한 통일성 있게 작성하였다.

 

main 함수의 for문에서는 getMaximum 함수를 작성할때에 얻은 방법에 착안하여 j 의 조건을 boardSize-1 로하여 null을 참조하는 일이 없도록 한 후, getMaximum에서 가로, 세로를 확인한 것과 같은 방식으로 i와 j의 위치를 바꿔가며 진행했다. swap 함수를 통하여 바뀐 board의 최댓값을 구해준뒤 동일한 swap 함수를 다시 실행시켜 원상태로 복구시켜 놓았다.

 

 

 

 

군대에서 무언가를 공부하기란 매우 어려운 일이다. 당장 이 문제를 처음 보고 나서는 일단 문제가 요구하는것을 이해만 한 뒤, 잠자리에 들기 전에 어떻게 구현해야할지 머릿속으로 계속 고민했다. 그렇게 고민했던 시간들이 있어 막상 코드를 적기 시작할때는 막힘없이 적어나갈 수 있었던 것 같다. 앞으로 다른 문제를 해결할 때에도 바로 코드를 작성하는 것보다 고민을 해보는 시간을 가져보는것이 문제를 더 빨리 풀 수도 있고, 시간도 더 절약할 수 있을 것 같다.