백준 3085 - 사탕게임 - 완전탐색

문제

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

풀이전략

1. 위치를 바꾸었을때 가로, 세로를 모두 확인해야 한다.
2. 완전탐색을 한다고 하더라도 50x50x2x50으로 1초안에 충분히 모든 값을 확인 할 수 있다. 따라서 충분히 완전탐색으로 해결 가능하다.
3. 재귀함수를 활용하여 현재위치와 이동방향에 따라 값을 확인한다.

코드

int n = 0; 
char mp[51][51]; /// 입력받을 판의 최대개수가 50개이므로
int res = -2147000000;
int dy[4] = {-1, 1, 0, 0}; /// 이동을 세로, 가로 이동하도록 direction에 따라 이동하도록 도와준다.
int dx[4] = {0, 0, 1, -1};

// 해당 direction으로 이동하였을 때 같은 문자가 얼마나 있는지 계산해주는 함수
int getCnt(int r, int c,int direction){
    int rr = r+dy[direction];
    int cc = c+dx[direction];
    // 이곳이 기저 사례로 판 밖으로 가버리면 그냥 return 해준다.
    if(rr>n || cc>n || rr == 0 || cc == 0){
        return 0;
    }
    else{
    	// 만약 이동할 칸과 문자가 같을 경우 값을 증가시키며 반복한다.
        if(mp[r][c] == mp[rr][cc]){
            return 1 + getCnt(rr,cc, direction);
            
        }
    }
    return 0;
}
/// 한 칸을 체크하는 함수이다. 
void check(int r, int c){
    int tmp = 0;
    // 세로방향 체크
    for(int i=0; i<2; i++){
        tmp+= getCnt(r, c, i);
    }
    // 세로와 가로는 구분해야한다.
    if(tmp>res) res = tmp;
    tmp  = 0;
    // 가로방향 체크
    for(int i=2; i<4; i++){
        tmp+= getCnt(r, c, i);
    }
    if(tmp>res) res = tmp;
}

int main(){

    cin >> n;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> mp[i][j];
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=0; k<4; k++){
            	// 어차피 getCnt에서 걸러지므로 판의 범위를 넘어서더라도 그냥 진행해도 된다.
                int ii = i+dy[k];
                int jj = j+dx[k];
                /// swap을 활용하여 위치를 바꿔주었다. 
                swap(mp[i][j],mp[ii][jj]);
                check(i, j);    
                swap(mp[i][j],mp[ii][jj]);
                
            }
            
        }
    }
    /// 체크할때 본인칸은 더하지 않으므로 마지막에 1을 더해준다.
    cout<<res+1<<endl;

    
    return 0;
}

소감

예전에 오목을 한번 만들어 본적이 있어서 그것과 비슷하게 코드를 짯기 때문에 수월하게 풀었다. 단... 가로, 세로 모두를 확인하는데에서 실수를 하였고, ii, jj 를 만들때 dy dx를 dy dy라고 적어 이를 찾는게 힘들었다. 역시 실수를 안하는것이 매우 중요하다.