[BF] 3085번 사탕 게임

3085번 사탕 게임

 

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

 

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

 

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

 

예제 입력

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

 

예제 출력

4

 

해결방법

모든 경우를 다 해보는 완전탐색 문제이다

 

• N ≤ 50
• 사탕을 바꿀 수 있는 기회는 한번
• 사탕을 바꾼 후, 최대 사탕 개수 구하기

 

일단 N의 조건이 N ≤ 50 이고 사탕을 바꾸는 횟수고 한번이기 때문에 그냥 다해보면 된다

 

(0,0) ~ (n-1,n-1) 까지 반복문을 돌며 주위의 사탕과 위치를 교환한다

사탕의 위치를 바꾼 뒤, 사탕의 최대 개수를 구하고 다시 위치를 복귀시킨다

void solve(int x,int y){
    int tmp;
    
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
        if(visited[nx][y]) continue;
        
        // 교환
        tmp = map[x][y];
        map[x][y] = map[nx][ny];
        map[nx][ny] = tmp;
        
        // 최대 사탕개수 파악
        ans = max(ans,eatCandy());
        
        // 원상복귀
        tmp = map[x][y];
        map[x][y] = map[nx][ny];
        map[nx][ny] = tmp;
    }
    
    visited[x][y] = true;
}

 

위치를 바꿨으면 이제 사탕의 최대 개수를 구한다

대각선의 노드들을 기준으로 행,열을 탐색하면 n번 반복하여 행, 열을 탐색한다

각각 행, 열은 n번씩 반복하여 최대 개수를 구할 수 있다

int eatCandy(){
    int res = 0;
    int cnt = 0;
    char pre = '0';
    
    for(int i=0; i<n; i++){
        // 행 검사
        cnt = 1;
        pre = map[0][i];
        for(int j=1; j<n; j++){
            if(pre == map[j][i]){
                cnt++;
            }
            else{
                res = max(res,cnt);
                pre = map[j][i];
                cnt = 1;
            }
        }
        res = max(res,cnt);
        
        // 열 검사
        cnt = 1;
        pre = map[i][0];
        for(int j=1; j<n; j++){
            if(pre == map[i][j]){
                cnt++;
            }else{
                res = max(res,cnt);
                pre = map[i][j];
                cnt = 1;
            }
        }
        res = max(res,cnt);
    }
    return res;
}

 

시간은 위치를 바꾸는데 4 * 2500 , 사탕의 최대 개수를 구하는데 50 * (50+50) 이다

따라서 시간복잡도는 O(5,000,000) 이므로 모든 경우를 탐색할 수 있다

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 51
#define INF 987654321
using namespace std;

int n,ans;

char map[MAX][MAX];
bool visited[MAX][MAX];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int eatCandy(){
    int res = 0;
    int cnt = 0;
    char pre = '0';
    
    for(int i=0; i<n; i++){
        // 행 검사
        cnt = 1;
        pre = map[0][i];
        for(int j=1; j<n; j++){
            if(pre == map[j][i]){
                cnt++;
            }
            else{
                res = max(res,cnt);
                pre = map[j][i];
                cnt = 1;
            }
        }
        res = max(res,cnt);
        
        // 열 검사
        cnt = 1;
        pre = map[i][0];
        for(int j=1; j<n; j++){
            if(pre == map[i][j]){
                cnt++;
            }else{
                res = max(res,cnt);
                pre = map[i][j];
                cnt = 1;
            }
        }
        res = max(res,cnt);
    }
    return res;
}

void solve(int x,int y){
    int tmp;
    
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
        if(visited[nx][y]) continue;
        
        // 교환
        tmp = map[x][y];
        map[x][y] = map[nx][ny];
        map[nx][ny] = tmp;
        
        // 최대 사탕개수 파악
        ans = max(ans,eatCandy());
        
        // 원상복귀
        tmp = map[x][y];
        map[x][y] = map[nx][ny];
        map[nx][ny] = tmp;
    }
    
    visited[x][y] = true;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
        }
    }
    
    ans = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            solve(i,j);
        }
    }
    cout << ans << "\n";
    
    return 0;
}