본문 바로가기
BOJ

BOJ 3085 사탕게임

by 홍code 2022. 3. 9.

문제링크 : https://www.acmicpc.net/problem/3085

 

3085번: 사탕 게임

예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

www.acmicpc.net

요약

주어진 문자(사탕색깔)로 이루어진 배열중에 딱한번 자신과 인접해있는 색이다른 사탕과 교환했을때 가로나, 세로로 인접해있는 같은 색의 사탕의 연속갯수가 가장 큰 값을 구하시오. (예제 출력을 보면 알수 있지만 한줄의 가로줄, 한줄의 세로줄이다!)

풀이

구현이 좀 까다롭다.. 사탕 보드의 개수가 최대 50x50이고 인접한 칸끼리 바꿀수 있는 최대 경우의 수도 50x49x2임으로 완전탐색으로 모두 바꿀수 있는 경우를 전부 해보고 바꿀떄마다 포문으로 바뀌는 사탕이 포함된 가로 세로줄을 확인해서 인접한 최대갯수를 확인해주면 된다.

코드

#include<iostream>
using namespace std;
int n,change,cnt, big;
char arr[51][51];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf(" %1c", &arr[i][j]);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n-1; j++) {
				change = arr[i][j];
				arr[i][j] = arr[i][j+1];
				arr[i][j+1] = change;
			cnt = 1;
			for (int k = 0; k < n-1; k++) {
				if (arr[i][k] == arr[i][k+1]) {
					cnt++;
					if (big < cnt)big = cnt;
				}
				else cnt = 1;
			}
			cnt = 1;
			for (int k = 0; k < n-1; k++) {
				if (arr[k][j] == arr[k+1][j]) {
					cnt++;
					if (big < cnt)big = cnt;
				}
				else cnt = 1;
			}
			cnt = 1;
			for (int k = 0; k < n; k++) {
				if (arr[k][j+1] == arr[k+1][j+1]){
					cnt++;
					if (big < cnt)big = cnt;
				}
				else cnt = 1;
			}
			arr[i][j+1] = arr[i][j];
			arr[i][j] = change;
		}
	}
	for (int j = 0; j < n; j++) {
		for (int i = 0; i < n-1; i++) {
				change = arr[i][j];
				arr[i][j] = arr[i+1][j];
				arr[i+1][j] = change;
			
			cnt = 1;
			for (int k = 0; k < n - 1; k++) {
				if (arr[k][j] == arr[k+1][j]) {
					cnt++;
					if (big < cnt)big = cnt;
				}
				else cnt = 1;
			}
			cnt = 1;
			for (int k = 0; k < n - 1; k++) {
				if (arr[i][k] == arr[i][k+1]) {
					cnt++;
					if (big < cnt)big = cnt;
				}
				else cnt = 1;
			}
			cnt = 1;
			for (int k = 0; k < n; k++) {
				if (arr[i+1][k] == arr[i+1][k+1]) {
					cnt++;
					if (big < cnt)big = cnt;
				}
				else cnt = 1;
			}
			arr[i+1][j] = arr[i][j];
			arr[i][j] = change;
		}
	}
	printf("%d", big);
}

'BOJ' 카테고리의 다른 글

BOJ 1018 체스판 다시 칠하기  (0) 2022.03.09
BOJ 2503 숫자야구  (0) 2022.03.09
BOJ 10448 유레카 이론  (0) 2022.03.09
BOJ 2231 분해합  (0) 2022.03.09
BOJ 2309 일곱난쟁이  (0) 2022.03.09

댓글