개요

[링크] 백준 3085번: 사탕 게임

n x n 개의 판에 다른 색의 사탕이 나열되어 있고
두 개를 골라 자리를 바꿨을 때
연속되는 색의 사탕의 최대 갯수를 구하는 문제

접근 방식

• 처음 접근 방법:
  사탕을 두 개 골라 바꾼 후
  만약 가로로 바꿨다면 해당 가로줄 다 비교해
  제일 길게 연속된 수 출력하고,
  세로로 바꿨다면 해당 세로줄 다 비교해
  제일 길게 연속된 수 출력하는 방식으로 접근했다.

  하지만 가로로 바꿨을 때 바뀐 두 사탕의 세로 줄이
  길게 연속된 수일 수도 있다는걸 간과했다.

• 두번째 접근 방법:
  만약 가로로 바뀌었을 땐 해당 가로줄을 비교하고
  바뀐 각각의 사탕의 세로줄들을 비교해 총 세번 비교하고,
  세로로 바뀌었을 땐 해당 세로줄,
  바뀐 각각 사탕의 가로줄들을 비교해 총 세번 비교해
  총 6번 비교하였다.

(그림으로 나타내봤는데 너무 저퀄이네요..)

각각의 비교 당 O(n)의 시간복잡도에
6번 비교한다고 해도 6은 상수취급으로 날아가서 상관없고,
처음 사탕 두개 집을 때 O(n^2), 집고 비교할때 O(n)이므로
총 시간복잡도는 O(n^3)이지만 애초에 크기 범위가
3~50이라 상관없다고 판단했다.

코드

#include<iostream>

using namespace std;

char** arr;					//사탕색 배열

void input(int& row) {		//입력값 받는 함수
	cin >> row;				//사탕 배열 동적 할당
	arr = new char*[row];
	for (int i = 0; i < row; i++) {
		arr[i] = new char[row];
	}
	for (int i = 0; i < row ; i++) {	//입력받음
		for (int j = 0; j < row; j++) {
			char temp;
			cin >> temp;
			arr[i][j]=temp;
		}
	}

}
int checkPair(const int& i,const int& j,const int& row) {	//arr[i][j]일 때, arr[i][j]값 바로 오른쪽값과 밑의 값 비교하는 함수	
													
	int sum=0;								//각 checkPair함수에서 제일 긴 연속수
	
	if (i + 1 != row) {										//arr[i][j]값과 그 밑 값 바꾸깅
		swap(arr[i][j], arr[i + 1][j]);						//arr[i][j]값과 그 밑의 값 바꿀때 j열 조사
		for (int idx = 0; idx < row; idx++) {				
			int sumTemp = 1;
			int idxTemp = idx;
			while (idxTemp + 1 < row) {							//열+1이 row보다 작을때까지
				if (arr[idxTemp][j] == arr[idxTemp + 1][j]) {	//해당 열의 값과 그다음 열값 비교후
					sumTemp++;									//같으면 sumTemp+1,idx++반복
					idxTemp++;
				}
				else
					break;

			}
			sum= sum> sumTemp ? sum: sumTemp;
		}
		for (int idx = 0; idx < row; idx++) {				//arr[i][j]값과 그 밑의 값 바꿀 때 i행 조사
			int sumTemp = 1;
			int idxTemp = idx;
			while (idxTemp + 1 < row) {						//열+1이 row보다 작을때까지
				if (arr[i][idxTemp] == arr[i][idxTemp+1]) {	//해당 열의 값과 그다음 열값 비교후
					sumTemp++;								//같으면 sumTemp+1,idx++반복
					idxTemp++;
				}
				else
					break;

			}
			sum= sum> sumTemp ? sum: sumTemp;

		}
		for (int idx = 0; idx < row; idx++) {				//arr[i][j]값과 그 밑의 값 바꿀 때 i+1행 조사
			int sumTemp = 1;
			int idxTemp = idx;
			while (idxTemp + 1 < row) {								//열+1이 row보다 작을때까지
				if (arr[i+1][idxTemp] == arr[i+ 1][idxTemp+1]) {	//해당 열의 값과 그다음 열값 비교후
					sumTemp++;										//같으면 sumTemp+1,idx++반복
					idxTemp++;
				}
				else
					break;

			}
			sum= sum> sumTemp ? sum: sumTemp;

		}
		swap(arr[i][j], arr[i + 1][j]);					//다시 바꿔주기
	}
	if (j + 1 != row) {									//arr[i][j]값과 오른쪽 값 바꾸기
		swap(arr[i][j], arr[i][j + 1]);					//바꿔주기

		for (int idx = 0; idx < row; idx++) {			//i,j값과 오른쪽 값 바꿀 때, i행 조사
			int sumTemp = 1;							//임시 합 저장하는 변수
			int idxTemp = idx;
			while (idxTemp + 1 < row) {							//행+1 값이 끝이 아닐때까지
				if (arr[i][idxTemp] == arr[i][idxTemp + 1]) {	//만약 다음 행값과 같다면
					sumTemp++;									//임시 합+1
					idxTemp++;									
				}
				else
					break;
			}
				sum= sum> sumTemp ? sum: sumTemp;
			
		}
		for (int idx = 0; idx < row; idx++) {			//i,j값과 오른쪽 값 바꿀때, j열 조사
			int sumTemp = 1;							//임시 합 저장하는 변수
			int idxTemp = idx;
			while (idxTemp + 1 < row) {							//행+1 값이 끝이 아닐때까지
				if (arr[idxTemp][j] == arr[idxTemp + 1][j]) {	//만약 다음 행값과 같다면
					sumTemp++;									//임시 합+1
					idxTemp++;									//++
				}
				else
					break;
			}
				sum= sum> sumTemp ? sum: sumTemp;
			
			
		}
		for (int idx = 0; idx < row; idx++) {			//i,j값과 오른쪽 값 바꿀때, j+1열 조사
			int sumTemp = 1;							//임시 합 저장하는 변수
			int idxTemp = idx;
			while (idxTemp + 1 < row) {									//행+1 값이 끝이 아닐때까지
				if (arr[idxTemp][j + 1] == arr[idxTemp + 1][j + 1]) {	//만약 다음 행값과 같다면
					sumTemp++;											//임시 합+1
					idxTemp++;											//++
				}
				else
					break;
			}
				sum= sum> sumTemp ? sum: sumTemp;
			
		}

		swap(arr[i][j], arr[i][j + 1]);					//다시 바꿔주기
	}

	return sum;
}
void solution(int& row) {											//답 도출 함수
	int ans=0;														//답 변수
	for (int i = 0; i < row; i++) {									//사탕 한개 고른 후
		for (int j = 0; j < row; j++) {					
			ans=checkPair(i, j,row)>ans ? checkPair(i, j, row):ans;	//checkpair함수로 그 한 개랑 오른쪽 바꿨을 때랑
																	//밑에랑 바꿨을 때 제일 긴 수를 답 변수랑 비교,
																	//더 큰값 변수에 넣어줌
		}
	}
	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);					
	int row = 0;
	input(row);
	solution(row);

	delete[] arr;
}

문풀후생

일단 2차원 배열 동적할당을 공부해본 문제였습니다.
매 값마다 위아래, 양옆으로 일 때, 위아래 옆
총 6가지로 세분하는 복잡한 문제여서
많이 생각해본 문제라 도움이 많이 되었던 것 같습니다.