상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'
using namespace std;
int check(vector<vector<char>>& v,int n, int y, int x)
{
char start_row = v[0][x];
char start_col = v[y][0];
int row_cnt = 1;
int col_cnt = 1;
int max_cnt = 0;
for(int i=1; i < n; i++)
{
if(start_row==v[i][x])
{
row_cnt++;
}
else
{
start_row = v[i][x];
row_cnt = 1;
}
if(start_col==v[y][i])
{
col_cnt++;
}
else
{
start_col = v[y][i];
col_cnt = 1;
}
max_cnt = max(row_cnt,max(col_cnt, max_cnt));
}
return max_cnt;
}
void swap(vector<vector<char>>& v,int y, int x, int mode)
{
char tmp;
if(!mode)
{
tmp=v[y][x];
v[y][x]=v[y][x+1];
v[y][x+1]=tmp;
}
else
{
tmp=v[y][x];
v[y][x]=v[y+1][x];
v[y+1][x]=tmp;
}
return;
}
int main()
{
FASTio;
int n;
cin >> n;
vector<vector<char>> v(n,vector<char> (n,0));
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
cin >> v[i][j];
int max_cnt = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(j!=n-1)
{
swap(v,i,j,0);
max_cnt = max(max_cnt,check(v,n,i,j));
max_cnt = max(max_cnt,check(v,n,i,j+1));
swap(v,i,j,0);
}
if(i!=n-1)
{
swap(v,i,j,1);
max_cnt = max(max_cnt,check(v,n,i,j));
max_cnt = max(max_cnt,check(v,n,i+1,j));
swap(v,i,j,1);
}
}
}
cout << max_cnt << endl;
return 0;
}
처음에는 그래프 문제인가 싶었는데 제한시간, 들어오는 데이터양을 보니 그래프 문제는 아닌 것을 파악하고 단순 구현 문제인 걸 알았다. 그 뒤로 어떻게 하면 코드의 양을 줄일 수 있을까 생각해봤다.
일단 입력을 받고 두 색을 교환하는 것을 해당 인덱스 기준 오른쪽, 아래쪽으로만 바꿀 수 있다고 정의했다. 왜냐하면 왼쪽, 위쪽으로 교환하는 경우는 이미 오른쪽, 아래쪽으로 교환했을 때 발생하는 경우라 따로 생각하지 않기로했다. 그리고 맨 오른쪽 열은 오른쪽으로, 맨 아래쪽 행은 아래쪽으로 교환 할 수 없어서 따로 조건문으로 해결을 해줬다.
그리고 한 번 교환으로 해당 인덱스와 교환된 인덱스를 한 번에 탐색을 진행했다.
제대로 동작하지 않아 10분 정도 디버깅 끝에 비슷한 코드를 복붙하는 과정에서 변수를 고치지 않았던 것이 문제였다.. 이런 자잘한 실수가 많아서 디버깅에서 시간을 많이 쏟는 거 같아 꼭 고쳐야 될 문제인 것 같다.