[알고리즘]BOJ_3085(사탕 게임)

Jongwon·2021년 8월 20일
0

algorithm

목록 보기
41/46

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

문제

상근이는 어렸을 적에 "봄보니 (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분 정도 디버깅 끝에 비슷한 코드를 복붙하는 과정에서 변수를 고치지 않았던 것이 문제였다.. 이런 자잘한 실수가 많아서 디버깅에서 시간을 많이 쏟는 거 같아 꼭 고쳐야 될 문제인 것 같다.

0개의 댓글