(백준 3085번 사탕게임 C++) 라이님 블로그 대회 알고리즘 따라잡기 2) 완전탐색(Brute-force Search) 4탄

오늘도 뚠뚠 개미는 뚠뚠 - 반차내고 알고리즘 문제 푸는 나 좀 멋찌다.

(결국 당일에는 못 품 ㅠㅠ 푸는데 3일 걸린거 실화냐!!!!!🙄🙄🙄🙄🙄🙄🙄)

 

완전탐색 포스팅3탄은 아래와 같습니당↓

2023.12.21 - [알고리즘] - (백준 2503번 숫자야구 C++) 라이님 블로그 대회 알고리즘 따라잡기 2) 완전탐색(Brute-force Search) 3탄

(백준 2503번 숫자야구 C++) 라이님 블로그 대회 알고리즘 따라잡기 2) 완전탐색(Brute-force Search) 3탄

 

백준 3085번 사탕게임

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

3085번: 사탕 게임

 

배경지식

1. 2차원 포인터

https://jjunsu.tistory.com/24

C언어 - 다차원 배열과 포인터의 관계

 

2. C++ Visual studio의 문자 간격이 벌어질 때

 

모기짱. 한컴 입력기 말고 Microsoft 입력키 쓰세요.(원래 Alt + '=' 누르면 돌아온다고 했는데 이번엔 작동안함 ㅠㅠ)

 

문제풀이 과정

나의 문제풀이 과정은 아래와 같다. (지금의 나도 헷갈리는데 이 글을 읽는 사람은 얼마나 헷갈릴까 싶어 적어본다)

 

우선 내가 만든 Array는 다음과 같다. 

ArrCandy에 input을 받고(아니 Candy 인데 y 오디갔찡) 이걸 y = x대칭해서 ArrCandy_symm을 만든다.

이렇게 한 이유는 모든 함수는 행에 대해 작동(Row 기준)하도록 하고 ArrCandy_symm을 이용해서 열에 대해서도 동일한 함수를 사용하기 위함이다.

 

그다음에 각 행과 열에 연속하는 최대 사탕갯수를 ArrCandy_RC에 저장했다.

이유는 문제 조건처럼 마주하는 사탕을 바꾸면 (행 기준) 그 사탕을 포함하는 행 1개 + 열 2개의 최대 연속사탕갯수만 바뀌게 되는데, 이 부분만 다시 계산해주고 싶었기 때문이다.

즉, 예시로 보면 ↔파란색 화살표에 의해 두 개의 사탕이 위치가 바뀌면 노란색으로 색칠한 부분만 고려해주면 된다는 의미다. (지금 예시는 N = 3일 때라서 쓸데없는 것처럼 보여도, N의 크기가 커지면 불필요한 연산을 줄일 수 있다고 생각했다.)

 

그러면 다음과 같이 2N개의 원소를 갖는 배열에서 3개의 원소만 수정하면 된다!

이렇게 ArrCandy_RC를 업데이트해주면서 가장 큰 숫자를 찾아 반환해주었다.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <iostream>

enum { ROW = 0, COLUMN = 1 }; 
int FindMaxCandy(int N,char ArrCandy[][50], int(*ArrCandy_RC)[50], int RC);
void CountMaxCandy(int N,  char ArrCandy[][50], int (*ArrCandy_RC)[50], int RC);
void ReflectCandy(int N, char ArrCandy[][50], char ArrCandy_symm[][50]);
int FindMax2DArr(int N, int ArrCandy_RC[][50]);

int main() {
	int N; char ch_temp; int result;
	scanf("%d", &N);
	char ArrCandy[50][50], ArrCandy_symm[50][50];		// input을 받음
	int ArrCandy_RC[2][50] = { 0 };						// 각각의 행(Row)과 열(Column)의 최대 일렬의 사탕 갯수를 저장

	for (int i = 0; i < N; i++) {
		scanf("%c", &ch_temp); // 공백 받아서 버리기		
		for (int j = 0; j < N; j++) {
			scanf("%c", &ArrCandy[i][j]);
		}
	}
	CountMaxCandy(N, ArrCandy, ArrCandy_RC, ROW);
	ReflectCandy(N, ArrCandy, ArrCandy_symm);
	CountMaxCandy(N, ArrCandy_symm, ArrCandy_RC, COLUMN);
	result = std::max(FindMaxCandy(N, ArrCandy, ArrCandy_RC, 0), FindMaxCandy(N, ArrCandy_symm, ArrCandy_RC, 1));
	printf("%d", result);
	return 0;
}

//char input을 받을 때는 공백을 조심하자!!
//CountMaxCandy
//각 줄의 최대 사탕배열의 크기를 저장하는 함수
//행의 최대 사탕배열은 첫번째 row에 저장
//열의 최대 사탕배열은 두번째 row에 저장
void CountMaxCandy(int N, char ArrCandy[][50], int(*ArrCandy_RC)[50],int RC) {
	int MAX_R = 1; char ch_temp; int result = 1;
	for (int i = 0; i < N; i++) {
		MAX_R = 1; result = 1;
		for (int j = 0; j < N-1; j++) {
			if (ArrCandy[i][j] == ArrCandy[i][j + 1]) MAX_R++;
			else MAX_R = 1;
			result = std::max(MAX_R, result);
		}	
		ArrCandy_RC[RC][i] = result;
	}
}

//ReflectCandy
//2차원 배열을 대칭시켜주는 함수
void ReflectCandy(int N, char ArrCandy[][50], char ArrCandy_symm[][50]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ArrCandy_symm[i][j] = ArrCandy[j][i];
		}
	}
	return;
}
int FindMax2DArr(int N, int ArrCandy_RC[][50]) {
	int result = 0;

	for (int i= 0; i < 2; i++) {
		for (int j = 0; j < N; j++) result = std::max(ArrCandy_RC[i][j], result);
	}
	return result;
}

int FindMaxCandy(int N, char ArrCandy[][50], int(*ArrCandy_RC)[50], int RC){
	char temp; int temp1, temp2, temp3; int answer = 0;
	int MAX_R = 1; char ch_temp; int result = 1;
	int RC_temp = std::abs(RC - 1);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N-1; j++) {
			if (ArrCandy[i][j] == ArrCandy[i][j + 1]) continue;

			temp = ArrCandy[i][j];
			ArrCandy[i][j] = ArrCandy[i][j + 1];
			ArrCandy[i][j + 1] = temp;

			temp1 = ArrCandy_RC[RC][i];
			temp2 = ArrCandy_RC[RC_temp][j];
			temp3 = ArrCandy_RC[RC_temp][j + 1];
			
			//temp1 부분
			MAX_R = 1; result = 1;

			for (int k = 0; k < N - 1; k++) {
				if (ArrCandy[i][k] == ArrCandy[i][k + 1]) MAX_R++;
				else MAX_R = 1;
				result = std::max(MAX_R, result);
			}
			ArrCandy_RC[RC][i] = result;

			//temp2 & temp3부분
			for (int l = j; l < j+2; l++) {
				MAX_R = 1; result = 1;
				for (int k = 0; k < N - 1; k++) {
					if (ArrCandy[k][l] == ArrCandy[k+1][l]) MAX_R++;
					else MAX_R = 1;
					result = std::max(MAX_R, result);
				}
				ArrCandy_RC[RC_temp][l] = result; 
			}
			
			answer = std::max(FindMax2DArr(N, ArrCandy_RC), answer);

			if (answer == N) return answer;

			//원래대로 되돌리기
			ArrCandy[i][j + 1] = ArrCandy[i][j];
			ArrCandy[i][j] = temp;

			ArrCandy_RC[RC][i] = temp1;
			ArrCandy_RC[RC_temp][j] = temp2; 
			ArrCandy_RC[RC_temp][j + 1] = temp3;
		}
	}
	return answer;

}

 

 

오늘의 실수

1. char형 input을 받을때는 공백을 조심해야 한다. 문제의 input을 보면 공백이 있는데, scanf를 이용해 char arr[i][j]로 input을 받을 경우 공백도 한자리를 차지하게 된다. 

2. continue를 하면 뒤 코드를 실행하지 않는다. continue를 넣는다면 이 부분을 조심해야 한다!!!

3. 이차원 배열을 사용한다면 행열을 잘 구분해서 사용해야 한다.

나는 for loop을 돌리는데 [i+1][j]를 써야 했는데 [i][j+1]을 써서 디버깅하는데 한참 걸렸따...

 

과거의 나는 매번 확인해서 풀었었네,,, 다 풀고 나니 이게 나은거 같기도 하다.😑

 

과거의 내 코드

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

char Arr[52][52];
int N,ans;

bool isInside(int x,int y) return (x>=0 && x < N) && (y>=0 && y<N);

void candy(){
	for(int i=0;i<N;i++){
		int cnt = 1;
		for(int j=0;j<N;j++){

			if(isInside(i,j+1) && Arr[i][j] == Arr[i][j+1]) cnt++;
			else {
				ans = max(ans, cnt);
				cnt = 1;
			}
		}
	}

	for(int i=0;i<N;i++){
		int cnt = 1;
		for(int j=0;j<N;j++){
			if(isInside(j+1,i) && Arr[j+1][i] == Arr[j][i]) cnt ++;
			else{
				ans = max(ans, cnt);
				cnt = 1;
			}
		}
	}
}

int main(){
	scanf("%d", &N);
	char ch;
	scanf("%c", &ch);
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			char tp;
			scanf("%c", &tp);
			if(tp!='\n' && tp != 0) Arr[i][j] = tp;
			else {scanf("%c", &tp);
				Arr[i][j] = tp;
			}
		}
	}
	
	int max_V = 0;

	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(isInside(i+1,j)){
				swap(Arr[i][j], Arr[i+1][j]);
				candy();
				swap(Arr[i][j], Arr[i+1][j]);
			}
		}
	}

	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(isInside(i,j+1)){
				swap(Arr[i][j+1], Arr[i][j]);
				candy();
				swap(Arr[i][j+1], Arr[i][j]);
			}
		}
	}
	printf("%d", ans);

}