[C++] 백준 3085

1. 문제

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

3085번: 사탕 게임

 

2. 고려사항

(1) main함수 ( 편의상 2차원 배열을 NxN 행렬이라 표현하겠음 )

• N 입력받으면 동적할당 이용하여 2차원 배열 생성 후 모든 요소 값 입력
• NxN 행렬에서 i=0~N, j=0~N까지 반복문을 돌리면서 값이 다르면 swap을 해준다
• 이때, 굳이 행렬 요소의 동서남북 체크 필요 없이 오른쪽, 아래방향으로만 체크해나감(뻗어나간다고 생각)
  →  ex.arr[0][1]과 이 요소의 오른쪽 arr[0][2]를 swap했다면 arr[0][2]일땐 왼쪽을 검사할 필요 없음
• 이때, 배열 int dx[2]={0,1}과 int dy[2]={0,1}이용하여 요소의 오른쪽, 아래 방향 chk
  → 인덱스 범위 벗어나는 경우 방지하기 위해 인덱스가 N보다 크거나 같으면 continue 구문 수행
• 행렬의 기준요소와 오른쪽 또는 아래쪽 요소의 값이 다르면 swap함수 이용해 값 바꿔주고 findMax 함수 통해 NxN행렬에서 모든 행과 열에 대해 최대값 찾음
• 이때 최대값이 N과 같다면 더이상 검사할 필요가 없으므로 값 출력하고 종료
• 아니라면 다시 동작 수행해야하기에 다시 swap함수 이용해 행렬 원래대로 되돌려놓음

(2) findMax 함수 (최종 최대값을 저장할 res는 전역변수로 선언하고 1로 초기화한다)

• 첫 번째로 NxN 행렬의 모든 각 행에 대해서 최댓값을 찾는다
  • 각 행에서 각 요소에 대해 오른쪽 요소와 값이 같으면 cnt ++ (ex. RR)
    → #include <algorithm>에 있는 max함수 통해 현재 cnt와 최종 최댓값(res)을 비교하며 update
  • 다르면 cnt=1로 초기화 (ex. RL)
• 두 번째로 NxN 행렬의 모든 각 열에 대해서 최댓값을 찾는다
  • 각 행에서 각 요소에 대해 오른쪽 요소와 값이 같으면 cnt ++ (ex. RR)
    → #include <algorithm>에 있는 max함수 통해 현재 cnt와 최종 최댓값(res)을 비교하며 update
  • 다르면 cnt=1로 초기화 (ex. RL)
• 최종적으로 res에 저장된 값이 해당 NxN행렬의 모든 열과 행에 대해서 같은 요소로 이루어져있는 가장 긴 연속 부분의 길이이다

 

2-1. 수도코드 작성

 

 

3. 소스코드

#include <iostream>
#include <cassert>
#include <cstdlib>
#include <algorithm>

using namespace std;
int res=1;
void findMax(char **(&candy), int N){
	//row
	
	for(int i=0;i<N;i++){
		int cnt=1;
		for(int j=0;j<N-1;j++){
			if(candy[i][j]==candy[i][j+1]){
				cnt++;
				res= max(res, cnt);
			}else{
				cnt=1;
			}
		}
	}
    
	for(int i=0;i<N;i++){
		int cnt=1;
		for(int j=0;j<N-1;j++){
			if(candy[j][i]==candy[j+1][i]){
				cnt++;
				res= max(res,cnt);
			}else{
				cnt=1;
			}
		}
	}
}

void swap(char &x, char &y){
	char temp = x;
	x = y;
	y=temp;
}

int main(){
	int N;
	cin >> N;
	char **candy= new char*[N]();
	assert(candy!=NULL);
	for(int i=0;i<N;i++){
		candy[i] = new char[N]();
		assert(candy[i]!=NULL);
	}
	
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			cin >> candy[i][j];
		}
	}
	//east south 
	int dx[2]={0,1};
	int dy[2]={1,0};
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			for(int k=0;k<2;k++){
				int x = i+dx[k];
				int y = j+dy[k];
				if(x>=N || y>=N){
					continue;
				}
				if(candy[i][j]!=candy[x][y]){
					swap(candy[i][j], candy[x][y]);
					findMax(candy, N);
					if(res==N){
						cout << res ;
						return 0;
					}
					swap(candy[i][j], candy[x][y]);
				}
			}
		}
	}
	cout << res;
	return 0;
}