백준 3085 - 사탕 게임
Updated:
C++
3085 번 - 사탕 게임
문제
상근이는 어렸을 적에 “봄보니 (Bomboni)” 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
문제 출처
접근 방법
모든 인접한 사탕을 교환해보며, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분을 센다.
인접한 사탕을 [가로 / 세로] 2가지 경우로 바꾸는 방법이 있으며,
사탕을 교환 할 때마다 전체 보드를 확인하는 것은 낭비이므로, 사탕을 교환 된 열/행만 확인한다.
구현
InitChk()
처음 주어진 보드의 사탕들을 탐색하며 한 줄에 연속 된 사탕 수를 센다.
사탕의 종류를 비교하며, 종류가 다른 사탕이 나올 시 현재까지 센 같은 종류의 사탕의 개수를 확인한다.
이후 사탕의 종류와 개수를 갱신한다.
이 포멧을 이후 사탕을 교환 하였을 시에도 똑같이 사용하여 가장 긴 연속 된 사탕 수를 센다.
cntCandy()
해당 문제는 시간 초과의 여유가 있어, 사탕을 교환 할 때마다 보드 전체의 사탕들을 확인하여도 된다.
하지만 이를 몰랐던 나는 최대한 시간 초과를 피하기 위하여, 교환 된 사탕에 영항을 받는 열과 행 3줄을 비교하도록 구현하였다.
만약 세로로 사탕을 교환하면, 가로 2줄 / 세로 1줄이 영향을 받는다. 따라서 이 줄만 연속 된 사탕의 수를 확인 하도록 하였다.
가로로 교환 하였다면, 가로 1줄 / 세로 2줄을 확인한다.
해당 함수를 호출 할 때 인자로 교환 하는 사탕의 위치, direction을 준다. direction을 통하여 세로로 교환하였는지, 가로로 교환하였는지 구분한다.
이후 InitChk()와 동일하게 연속 된 사탕의 개수를 센다.
나온 가장 큰 연속 된 사탕의 수를 전체 사탕의 수와 비교하여 갱신하여 해답을 구한다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>
using namespace std;
int result, n;
string candy[50];
void InitChk();
int cntCandy(int, int, char);
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
string temp;
for (int i = 0; i < n; i++) {
cin >> candy[i];
}
//초기 상태 그래프의 최대 크기의 사탕 개수를 센다.
InitChk();
//가로 방향으로 교환
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
swap(candy[i][j], candy[i][j + 1]);
result = max(result, cntCandy(i, j, 'x'));
swap(candy[i][j], candy[i][j + 1]);
}
}
//세로 방향으로 교환
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n; j++) {
swap(candy[i][j], candy[i + 1][j]);
result = max(result, cntCandy(i, j, 'y'));
swap(candy[i][j], candy[i + 1][j]);
}
}
cout << result << "\n";
return 0;
}
void InitChk() {
char curCx = 'A', curCy = 'A'; //사탕의 종류
int cntx = 1, cnty = 1; //연속된 사탕의 수
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//가로
if (candy[i][j] != curCx) { //사탕의 종류가 다를 시
result = max(cntx, result); //지금까지 센 연속된 사탕의 수와 비교
cntx = 1;
curCx = candy[i][j]; //현재 사탕 종류를 갱신
}
else {
cntx++;
}
//세로
if (candy[j][i] != curCy) {
result = max(cnty, result);
cnty = 1;
curCy = candy[j][i];
}
else {
cnty++;
}
}
curCx = 'A', curCy = 'A';
}
}
int cntCandy(int y, int x, char direction) {
int maxInt = 1;
char curC = 'A';
int cnt = 0;
if (direction == 'x') { // x축을 기준으로 사탕 2개를 회전 시켰을 시
//가로 확인
for (int i = 0; i < n; i++) {
if (candy[y][i] != curC) {
maxInt = max(maxInt, cnt);
cnt = 1;
curC = candy[y][i];
}
else {
cnt++;
}
}
maxInt = max(maxInt, cnt);
//세로 확인
for (int idx = 0; idx < 2; idx++) {
curC = 'A';
cnt = 0;
for (int i = 0; i < n; i++) {
if (candy[i][x + idx] != curC) {
maxInt = max(maxInt, cnt);
cnt = 1;
curC = candy[i][x + idx];
}
else {
cnt++;
}
}
maxInt = max(maxInt, cnt);
}
}
else { // y축을 기준으로 사탕 2개를 회전 시켰을 시
//세로 확인
for (int i = 0; i < n; i++) {
if (candy[i][x] != curC) {
maxInt = max(maxInt, cnt);
cnt = 1;
curC = candy[i][x];
}
else {
cnt++;
}
}
maxInt = max(maxInt, cnt);
//가로 확인
for (int idx = 0; idx < 2; idx++) {
curC = 'A';
cnt = 0;
for (int i = 0; i < n; i++) {
if (candy[y + idx][i] != curC) {
maxInt = max(maxInt, cnt);
cnt = 1;
curC = candy[y + idx][i];
}
else {
cnt++;
}
}
maxInt = max(maxInt, cnt);
}
}
return maxInt;
}
후기 및 개선할 점
cntCandy 함수 내부에 사탕 개수를 갱신하여 주는 부분을 빼먹어, 답이 계속하여 틀려 고생을 하였다.
또한 string을 입력 받아 배열로 저장하는데
