백준 삼성 SW 역량 테스트 기출 문제 문제풀이 / 2048 (Easy) (백준 12100번)

삼성 SW 역량테스트 기출문제인 2048을 풀어보겠습니다.

 

 

 

문제를 풀기 전 단계별로 생각하는것이 필요합니다.

 

우선 해당 문제는 2차원 배열을 1차원화 해서 다루었습니다 .  (이부분은 다른 게시글에 원리를 설명해두었습니다.)

 

저는 이 문제를 2048의 성질대로 구현만 잘 해놓는다면 , 이 가정하에 

각 방향별로 총 5번 선택하는 총 경우의 수를 탐색하면 된다고 풀었습니다.

 

총 경우의 수가 4^5 가 되겠죠.

2048은 같은 방향으로 두번이상도 선택할 수 있기때문에 매번 4방향을 탐색했습니다(재귀함수 이용)

기본적으로 재귀함수 부분만 설명드리면 어려울게없는 문제기때문에 재귀함수만 설명드리고 나머지는 질문이 있을경우만 올려드리도록 하겠습니다.

 

// direction 1 = left , 2 = right , 3 = up , 4 = down
int maxnum(int *Arr , int N , int direction, int count){
    
    //할당
    int *arr = (int*)malloc(sizeof(int)*N*N);
    int max =0,temp;
    
    //동기화
    for (int i=0;i<(N*N);i++){
        arr[i] = Arr[i];
    }
  
        
    if (count ==0){
        for (int i=1;i<5;i++){
            temp = maxnum(arr,N,i,(count+1));
            if (max<temp){
                max = temp;
            }
        }
    }
    else if(count<=5){
        switch (direction)
        {
            case 1:
                left(&arr,N);
            break;

            case 2:
                right(&arr,N);
            break;

            case 3:
                up(&arr,N);
            break;

            case 4:
                down(&arr,N);
            break;

        default:
            break;
        }
        for (int i=1;i<5;i++){
            temp = maxnum(arr,N,i,(count+1));
            if (max<temp){
                max = temp;
            }
        }
    }
    else{
        for (int i=0;i<(N*N);i++){
                if (max<arr[i]){
                    max = arr[i];
                }
            }
    }        
    free(arr);
    return max;
}

이 함수가 전체 탐색을 하여 max값을 계산하고 리턴하여주는 함수입니다. 매개변수로는 배열과 배열이 몇칸인지 , 그리고 방향과 회차카운트를 받습니다.

여기서 중요한것은 이전회차에서  넘어와서 direction 으로 이동하고 다음회차에 4방향을 탐색할것인데 , 4방향 탐색이 각각 독립적으로 일어나야하기때문에 , 배열은 각각 복사해서 사용합니다.

 

 

방금받은 이전회차 배열을 복사 후 , 다음회차에 각각 4방향을 넣어주는거죠  그리고 5회차까지 실행 후엔 가장 큰 값을 받아 리턴하고 그 각 경우의수별 리턴값을 비교하여 큰 값을 갱신시켜주는 알고리즘입니다.

 

 

아래는 전체 소스입니다

#include<stdio.h>
#include<stdlib.h>

void left(int **arr , int N){
    for (int i=0;i<(N*N);i++){
        if ((i%N)!=0){
            for (int j=i;arr[0][j-1]==0;j--)
            {
                if ((j%N)==0){
                    break;
                }
                arr[0][j-1] = arr[0][j];
                arr[0][j] = 0; 
            }
        }
    }
    for (int i=0;i<(N*N);i++){
        if ((i%N)!=0){
            if (arr[0][i]==arr[0][i-1]){
                arr[0][i-1] += arr[0][i];
                arr[0][i]=0;
            }
        }
    }
    for (int i=0;i<(N*N);i++){
        if ((i%N)!=0){
            for (int j=i;arr[0][j-1]==0;j--)
            {
                if ((j%N)==0){
                    break;
                }
                arr[0][j-1] = arr[0][j];
                arr[0][j] = 0;
            }
            
        }
    }
}

void right(int **arr , int N){
    for (int i=(N*N-1);i>=0;i--){
        if ((i%N)!=(N-1)){
            for (int j=i;arr[0][j+1]==0;j++)
            {
                if ((j%N)==(N-1)){
                    break;
                }
                arr[0][j+1] = arr[0][j];
                arr[0][j] = 0; 
            }
        }
    }
    for (int i=(N*N-1);i>=0;i--){
        if ((i%N)!=(N-1)){
            if (arr[0][i]==arr[0][i+1]){
                arr[0][i+1] += arr[0][i];
                arr[0][i]=0;
            }
        }
    }
    for (int i=(N*N-1);i>=0;i--){
        if ((i%N)!=(N-1)){
            for (int j=i;arr[0][j+1]==0;j++)
            {
                if ((j%N)==(N-1)){
                    break;
                }
                arr[0][j+1] = arr[0][j];
                arr[0][j] = 0; 
            }
        }
    }
}

void down(int **arr , int N){
    for (int i=(N*N)-N-1;i>=0;i--){
        for (int j=i;arr[0][j+N]==0;j=j+N){
            if(j>=(N*(N-1))){
                break;
            }
            arr[0][j+N] = arr[0][j];
            arr[0][j] = 0; 
        }
    }

    for (int i=(N*N)-N-1;i>=0;i--){
        if (arr[0][i]==arr[0][i+N]){
            arr[0][i+N] += arr[0][i];
            arr[0][i]=0;
        }
    }
    for (int i=(N*N)-N-1;i>=0;i--){
        for (int j=i;arr[0][j+N]==0;j=j+N){
            if(j>=(N*(N-1))){
                break;
            }
            arr[0][j+N] = arr[0][j];
            arr[0][j] = 0; 
        }
    }
}

void up(int **arr , int N){
    for (int i=N;i<(N*N);i++){
        for (int j=i;arr[0][j-N]==0;j=j-N){
            if (j<N){
                break;
            }
            arr[0][j-N] = arr[0][j];
            arr[0][j]=0;
        }
    }
    for (int i=N;i<(N*N);i++){
        if (arr[0][i]==arr[0][i-N]){
            arr[0][i-N] += arr[0][i];
            arr[0][i]=0;
        }
    }
    for (int i=N;i<(N*N);i++){
        for (int j=i;arr[0][j-N]==0;j=j-N){
            if (j<N){
                break;
            }
            arr[0][j-N] = arr[0][j];
            arr[0][j]=0;
        }
    }
}

// direction 1 = left , 2 = right , 3 = up , 4 = down
int maxnum(int *Arr , int N , int direction, int count){
    
    //할당
    int *arr = (int*)malloc(sizeof(int)*N*N);
    int max =0,temp;
    
    //동기화
    for (int i=0;i<(N*N);i++){
        arr[i] = Arr[i];
    }
  
        
    if (count ==0){
        for (int i=1;i<5;i++){
            temp = maxnum(arr,N,i,(count+1));
            if (max<temp){
                max = temp;
            }
        }
    }
    else if(count<=5){
        switch (direction)
        {
            case 1:
                left(&arr,N);
            break;

            case 2:
                right(&arr,N);
            break;

            case 3:
                up(&arr,N);
            break;

            case 4:
                down(&arr,N);
            break;

        default:
            break;
        }
        for (int i=1;i<5;i++){
            temp = maxnum(arr,N,i,(count+1));
            if (max<temp){
                max = temp;
            }
        }
    }
    else{
        for (int i=0;i<(N*N);i++){
                if (max<arr[i]){
                    max = arr[i];
                }
            }
    }        
    free(arr);
    return max;
}


int main(){
    int N;
    int *arr;
    scanf("%d",&N);
    //할당
    arr = (int*)malloc(sizeof(int)*N*N);
    //입력받기
    for (int i=0;i<(N*N);i++){
        scanf("%d",&arr[i]);
    }

    printf("%d",maxnum(arr,N,0,0));
    free(arr);
    return 0;
}

 

코드 상세설명 업데이트 예정