빠켱이

백준 12100번 2048(Easy)[C++] - 삼성SW 역량 테스트 기출문제 본문

알고리즘/백준 알고리즘

백준 12100번 2048(Easy)[C++] - 삼성SW 역량 테스트 기출문제

빠켱이 2021. 2. 4. 21:40

12100번은 브루트 포스 알고리즘 문제입니다.

위아래 왼쪽 오른쪽의 방향을 모두 탐색해서 결과를 도출하는 문제입니다.

코드를 구현하다 보니 재귀 함수와 방향을 이동하는 함수를 하나로 짜버렸는데,

재귀 함수와 이동 함수를 나누어 짜면 가독성에 좋을 것 같습니다.

 

숫자를 한 방향으로 이동했을 때 두 개의 숫자를 합치는 것과 공백을 고려하는 것은 queue를 사용하여 해결하였습니다.

 

고려사항 1. 두 개의 숫자만을 합쳐주는 것

해당 방향의 숫자들을 적절한 순서로 queue에 넣습니다.

(ex. 위로 이동하는 방향이면 위에서부터 아래로 queue에 대입)

queue를 앞에서 부터 탐색하며 조건에 맞게 위부터 채워나감니다.

 

고려사항 2. 공백 처리

queue를 사용하지 않으면 공백의 여부를 따로 처리해줘야 하지만

해당 코드에서는 빈 공간의 값이 0이므로 0이면 queue에 들어가지 않습니다.

따라서 queue를 사용하면 공백을 신경 쓰지 않고 짤 수 있기 때문에 좀 더 편리한 것 같습니다.

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n, result = 0;
int sudoku[21][21] = {0};
int d[4] = {0,1,2,3};     //0:상, 1:하, 2:좌, 3:우

void move(int dir, int count){
    if(count == 5){                 //5번 움직임
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                result = max(result, sudoku[i][j]);
        return;
    }
    int copy_sudoku[21][21] = {0};
    for(int i = 0; i < n; i++)              
            for(int j = 0; j < n; j++)
                copy_sudoku[i][j] = sudoku[i][j];   //현재 배열 복사
    if(dir == 0){                   //상
        for(int i = 0; i < n; i++){
            queue<int> q;
            for(int j = 0; j < n; j++){
                if(copy_sudoku[j][i])
                    q.push(copy_sudoku[j][i]);        //공백 제외한 숫자 q에 넣음
                sudoku[j][i] = 0;                           //스도쿠판 초기화
            }
            int j = 0;
            while(!q.empty()){
                if(q.size() >= 2){                          //queue에 2개 이상일 때
                    int tmp = q.front();
                    q.pop();
                    if(tmp == q.front()){                   //두개의 값이 같을 때
                        sudoku[j++][i] = q.front() * 2;     //첫번째 값 * 2 대입
                        q.pop();
                    }
                    else                                    //두개의 값이 다를 때
                        sudoku[j++][i] = tmp;
                }
                else{                                       //queue에 1개일 때
                    sudoku[j++][i] = q.front();             //첫번째 값 대입
                    q.pop();
                }
            }
        }
    }
    else if(dir == 1){              //하
        for(int i = 0; i < n; i++){
            queue<int> q;
            for(int j = n-1; j >= 0; j--){
                if(copy_sudoku[j][i])
                    q.push(copy_sudoku[j][i]);
                sudoku[j][i] = 0;
            }
            int j = n-1;
            while(!q.empty()){
                if(q.size() >= 2){
                    int tmp = q.front();
                    q.pop();
                    if(tmp == q.front()){
                        sudoku[j--][i] = q.front() * 2;
                        q.pop();
                    }
                    else
                        sudoku[j--][i] = tmp;
                }
                else{
                    sudoku[j--][i] = q.front();
                    q.pop();
                }
            }
        }
    }
    else if(dir == 2){              //좌
        for(int i = 0; i < n; i++){
            queue<int> q;
            for(int j = 0; j < n; j++){
                if(copy_sudoku[i][j])
                    q.push(copy_sudoku[i][j]);
                sudoku[i][j] = 0;
            }
            int j = 0;
            while(!q.empty()){
                if(q.size() >= 2){
                    int tmp = q.front();
                    q.pop();
                    if(tmp == q.front()){
                        sudoku[i][j++] = q.front() * 2;
                        q.pop();
                    }
                    else
                        sudoku[i][j++] = tmp;
                }
                else{
                    sudoku[i][j++] = q.front();
                    q.pop();
                }
            }
        }
    }
    else if(dir == 3){              //우
        for(int i = 0; i < n; i++){
            queue<int> q;
            for(int j = n-1; j >= 0; j--){
                if(copy_sudoku[i][j])
                    q.push(copy_sudoku[i][j]);
                sudoku[i][j] = 0;
            }
            int j = n-1;
            while(!q.empty()){
                if(q.size() >= 2){
                    int tmp = q.front();
                    q.pop();
                    if(tmp == q.front()){
                        sudoku[i][j--] = q.front() * 2;
                        q.pop();
                    }
                    else
                        sudoku[i][j--] = tmp;
                }
                else{
                    sudoku[i][j--] = q.front();
                    q.pop();
                }
            }
        }
    }
    for(int i = 0; i < 4; i++)
        move(i, count+1);
    for(int k = 0; k < n; k++)              
        for(int j = 0; j < n; j++)
            sudoku[k][j] = copy_sudoku[k][j];           //변경 전으로 배열 복귀
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            scanf("%d", &sudoku[i][j]);
    for(int i = 0; i < 4; i++)
        move(i, 0);
    printf("%d", result);
}
Comments