백준 12100번 : 2048(easy)

문제 링크: https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 문제 설명 

https://play2048.co/ 여기 들어가면 게임해볼수있다.

이 게임에서 현재 화면이 주어졌을때 최대 5번 움직여서 얻을 수있는 최대 값을 구하면 된다 .

배열이 계속 이상하게 넘어가서 3일걸린듯 . ㅠ ㅠ

 

 알고리즘 

 

기존 map                                                                             new map

 

위 그림 같이 타일 이있다고했을때 왼쪽 타일을 왼쪽으로 밀면 오른쪽 타일처럼 된다 . 여기서 알고리즘을 유추해보자.

 

1. 왼쪽에서 1번째 인덱스 확인 -> 아무것도 없으면 continue;

2. 2번째 인덱스 확인 -> 2를  num에  저장

3. 3번째 인덱스 확인 ->2 , 그런데 num 이랑 같다 - > 더해서 new map 맨 왼쪽부터 채움(new map idx 필요)

   -> num =0 초기화

4. 4번째 인덱스 확인 -> num = 4

5. 5번째 인덱스 확인 num이랑다르다 -> num을 new map idx 에 채우고 -> num = 8

6. num != 0일 때 더 이상 확인 할 인덱스가없다 -> num을 new map 에 채움

 

 

 

 코드 

#include<iostream>
#include<algorithm>
using namespace std;
 
 
 
int N;
int arr[21][21];
int new_map[21][21];
int map[21][21];
int result = 0;
 
 
//왼쪽으로 미는 함수
void left() {
    for (int i = 0; i < N; i++) {
 
        int num = 0;
        int idx = 0;
 
        for (int j = 0; j < N; j++) {
 
            //map[i][j] = 0 이면 continue;
            if (map[i][j] == 0)continue;
 
            else {
                //num 에 아무것도 저장되어 있지않을때
                if (num == 0) num = map[i][j];
 
                else {
 
                    //num에 저장된 숫자와 현재 map 의숫자가 동일할 때
                    if (num == map[i][j]) {
                        new_map[i][idx++] = num * 2;
                        num = 0;
                    }
                    //num에 저장된 숫자와 현재 map 의숫자가 동일 다를때
                    else {
                        new_map[i][idx++] = num;
                        num = map[i][j];
                    }
                }
            }
        }
 
        // 마지막에 num이 0이아니면 num을 new_map 에 추가
        if (num != 0) new_map[i][idx] = num;
 
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            //new_map을 map 에 넣어 주고 new_map 은 0으로 초기화
            map[i][j] = new_map[i][j];
            new_map[i][j] = 0;
        }
    }
}
 
//오른쪽으로 미는 함수
void right() {
    for (int i = 0; i < N; i++) {
 
        int num = 0;
        int idx = N - 1;
 
        for (int j = N - 1; j >= 0; j--) {
 
            //map[i][j] = 0 이면 continue;
            if (map[i][j] == 0)continue;
 
            else {
                //num 에 아무것도 저장되어 있지않을때
                if (num == 0) num = map[i][j];
 
                else {
 
                    //num에 저장된 숫자와 현재 map 의숫자가 동일할 때
                    if (num == map[i][j]) {
                        new_map[i][idx--] = num * 2;
                        num = 0;
                    }
                    //num에 저장된 숫자와 현재 map 의숫자가 동일 다를때
                    else {
                        new_map[i][idx--] = num;
                        num = map[i][j];
                    }
                }
            }
        }
 
        // 마지막에 num이 0이아니면 num을 new_map 에 추가
        if (num != 0) new_map[i][idx] = num;
 
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            //new_map을 map 에 넣어 주고 new_map 은 0으로 초기화
            map[i][j] = new_map[i][j];
            new_map[i][j] = 0;
        }
    }
}
 
//위쪽으로 미는 함수
void up() {
 
    for (int j = 0; j < N; j++) {
        int num = 0;
        int idx = 0;
 
        for (int i = 0; i < N; i++) {
 
            //map[i][j] = 0 이면 continue;
            if (map[i][j] == 0)continue;
 
            else {
                //num 에 아무것도 저장되어 있지않을때
                if (num == 0) num = map[i][j];
 
                else {
 
                    //num에 저장된 숫자와 현재 map 의숫자가 동일할 때
                    if (num == map[i][j]) {
                        new_map[idx++][j] = num * 2;
                        num = 0;
                    }
                    //num에 저장된 숫자와 현재 map 의숫자가 동일 다를때
                    else {
                        new_map[idx++][j] = num;
                        num = map[i][j];
                    }
                }
            }
        }
 
        // 마지막에 num이 0이아니면 num을 new_map 에 추가
        if (num != 0) new_map[idx++][j] = num;
 
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            //new_map을 map 에 넣어 주고 new_map 은 0으로 초기화
            map[i][j] = new_map[i][j];
            new_map[i][j] = 0;
        }
    }
}
//아래쪽으로 미는 함수
void down() {
 
    for (int j = 0; j < N; j++) {
        int num = 0;
        int idx = N-1;
 
        for (int i = N - 1; i >=0; i--) {
 
            //map[i][j] = 0 이면 continue;
            if (map[i][j] == 0)continue;
 
            else {
                //num 에 아무것도 저장되어 있지않을때
                if (num == 0) num = map[i][j];
 
                else {
 
                    //num에 저장된 숫자와 현재 map 의숫자가 동일할 때
                    if (num == map[i][j]) {
                        new_map[idx--][j] = num * 2;
                        num = 0;
                    }
                    //num에 저장된 숫자와 현재 map 의숫자가 동일 다를때
                    else {
                        new_map[idx--][j] = num;
                        num = map[i][j];
                    }
                }
            }
        }
 
        // 마지막에 num이 0이아니면 num을 new_map 에 추가
        if (num != 0) new_map[idx--][j] = num;
 
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            //new_map을 map 에 넣어 주고 new_map 은 0으로 초기화
            map[i][j] = new_map[i][j];
            new_map[i][j] = 0;
        }
    }
}
 
//배열에서 최대값
int check() {
    int num = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            num = max(num, map[i][j]);
        }
    }
    return num;
}
 
//재귀로 구현한 게임 
void func(int cnt) {
    
    //5번까지만
    if (cnt > 5)return;
 
    result = max(result, check());
 
    //현재 보드상태를 저장할 임시 보드
    int copyBoard[21][21];
 
    //현재 보드상태 임시 저장
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            copyBoard[i][j] = map[i][j];
        }
    }
    //오른쪽으로 밀고 재귀
    right();
    func(cnt + 1);
    //보드 복구
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
             map[i][j] = copyBoard[i][j];
        }
    }
 
    //왼쪽으로 밀고 재귀
    left();
    func(cnt + 1);
    //보드 복구
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            map[i][j] = copyBoard[i][j];
        }
    }
 
    //위로 밀고 재귀
    up();
    func(cnt + 1);
    //보드 복구
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            map[i][j] = copyBoard[i][j];
        }
    }
 
    //밑으로 밀고 재귀
    down();
    func(cnt + 1);
    //보드 복구
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            map[i][j] = copyBoard[i][j];
        }
    }
 
 
    
 
}
int main() {
 
    cin >> N;
 
    //기본 상태 삽입
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
    func(0);
    cout << result;
 
}

코드가 상당히긴데 보면 왼쪽 오른쪽 위쪽 아래쪽 으로 각각 미는 함수의 반복이다 .