본문 바로가기
Algorithm/삼성 SW 역량 테스트 기출 문제

[Baekjoon][12100] 2048 (Easy)

by 어발 2022. 1. 17.

출처 - 백준사이트

12100번: 2048 (Easy)

나의 풀이

#include <iostream>
#include <cstring>

#define MAX 20

using namespace std;

// 이동순서는 상 우 하 좌
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};

int N;
int map[MAX][MAX] = {0, };
int result = -1;

void print_map() {
    for (int y = 0 ; y < N ; y++) {
        for (int x = 0 ; x < N ; x++) {
            cout << map[y][x] << " ";
        }

        cout << "\n";
    }

    cout << "\n";
}

void add(int dir) {
    switch (dir) {
    case 0:
        // 0을 미는 로직.
        for (int x = 0 ; x < N ; x++) {
            int first_zero = -1;

            for (int y = 0 ; y < N ; y++) {
                if ((first_zero == -1) && (map[y][x] == 0)) // 이전에 0인 칸이 없었고, 현재가 0이면
                    first_zero = y;
                else if ((first_zero != -1) && (map[y][x] != 0)) { // 이전에 0인칸이 있고, 현재가 0이 아니면
                    map[first_zero][x] = map[y][x];
                    map[y][x] = 0;
                    first_zero++; // 이전에 0이었던 칸 다음칸은 무조건 0임.
                }
            }
        }

        for (int x = 0; x < N ; x++) {
            for (int y = 0 ; y < N - 1 ; y++) {
                if ((map[y][x] != 0) && (map[y][x] == map[y+1][x])) { // 현재위치가 0이 아닐때, 현재위치와 다음인덱스의 숫자가 같으면 더함.
                    map[y][x] += map[y+1][x];
                    map[y+1][x] = 0;
                    y++; // 어차피 다음인덱스는 0이니까 한칸 건너뜀.
                }
            }
        }

        // 0을 미는 로직.
        for (int x = 0 ; x < N ; x++) {
            int first_zero = -1;

            for (int y = 0 ; y < N ; y++) {
                if ((first_zero == -1) && (map[y][x] == 0)) // 이전에 0인 칸이 없었고, 현재가 0이면
                    first_zero = y;
                else if ((first_zero != -1) && (map[y][x] != 0)) { // 이전에 0인칸이 있고, 현재가 0이 아니면
                    map[first_zero][x] = map[y][x];
                    map[y][x] = 0;
                    first_zero++; // 이전에 0이었던 칸 다음칸은 무조건 0임.
                }
            }
        }

        break;
    case 1:
        // 0을 미는 로직.
        for (int y = 0 ; y < N ; y++) {
            int first_zero = -1;

            for (int x = N-1 ; x > -1 ; x--) {
                if ((first_zero == -1) && (map[y][x] == 0)) // 이전에 0인 칸이 없었고, 현재가 0이면
                    first_zero = x;
                else if ((first_zero != -1) && (map[y][x] != 0)) { // 이전에 0인칸이 있고, 현재가 0이 아니면
                    map[y][first_zero] = map[y][x];
                    map[y][x] = 0;
                    first_zero--; // 이전에 0이었던 이전칸은 무조건 0임.
                }
            }
        }

        for (int y = 0; y < N ; y++) {
            for (int x = N-1 ; x > 0 ; x--) {
                if ((map[y][x] != 0) && (map[y][x] == map[y][x-1])) { // 현재위치가 0이 아닐때, 현재위치와 다음인덱스의 숫자가 같으면 더함.
                    map[y][x] += map[y][x-1];
                    map[y][x-1] = 0;
                    x--; // 어차피 다음인덱스는 0이니까 한칸 건너뜀.
                }
            }
        }

        // 0을 미는 로직.
        for (int y = 0 ; y < N ; y++) {
            int first_zero = -1;

            for (int x = N-1 ; x > -1 ; x--) {
                if ((first_zero == -1) && (map[y][x] == 0)) // 이전에 0인 칸이 없었고, 현재가 0이면
                    first_zero = x;
                else if ((first_zero != -1) && (map[y][x] != 0)) { // 이전에 0인칸이 있고, 현재가 0이 아니면
                    map[y][first_zero] = map[y][x];
                    map[y][x] = 0;
                    first_zero--; // 이전에 0이었던 이전칸은 무조건 0임.
                }
            }
        }

        break;
    case 2:
        // 0을 미는 로직.
        for (int x = 0 ; x < N ; x++) {
            int first_zero = -1;

            for (int y = N-1 ; y > -1 ; y--) {
                if ((first_zero == -1) && (map[y][x] == 0)) // 이전에 0인 칸이 없었고, 현재가 0이면
                    first_zero = y;
                else if ((first_zero != -1) && (map[y][x] != 0)) { // 이전에 0인칸이 있고, 현재가 0이 아니면
                    map[first_zero][x] = map[y][x];
                    map[y][x] = 0;
                    first_zero--; // 이전에 0이었던 이전칸은 무조건 0임.
                }
            }
        }

        for (int x = 0; x < N ; x++) {
            for (int y = N-1 ; y > 0 ; y--) {
                if ((map[y][x] != 0) && (map[y][x] == map[y-1][x])) { // 현재위치가 0이 아닐때, 현재위치와 이전인덱스의 숫자가 같으면 더함.
                    map[y][x] += map[y-1][x];
                    map[y-1][x] = 0;
                    y--; // 어차피 이전인덱스는 0이니까 한칸 건너뜀.
                }
            }
        }

        // 0을 미는 로직.
        for (int x = 0 ; x < N ; x++) {
            int first_zero = -1;

            for (int y = N-1 ; y > -1 ; y--) {
                if ((first_zero == -1) && (map[y][x] == 0)) // 이전에 0인 칸이 없었고, 현재가 0이면
                    first_zero = y;
                else if ((first_zero != -1) && (map[y][x] != 0)) { // 이전에 0인칸이 있고, 현재가 0이 아니면
                    map[first_zero][x] = map[y][x];
                    map[y][x] = 0;
                    first_zero--; // 이전에 0이었던 이전칸은 무조건 0임.
                }
            }
        }

        break;
    case 3:
        // 0을 미는 로직.
        for (int y = 0 ; y < N ; y++) {
            int first_zero = -1;

            for (int x = 0 ; x < N ; x++) {
                if ((first_zero == -1) && (map[y][x] == 0)) // 이전에 0인 칸이 없었고, 현재가 0이면
                    first_zero = x;
                else if ((first_zero != -1) && (map[y][x] != 0)) { // 이전에 0인칸이 있고, 현재가 0이 아니면
                    map[y][first_zero] = map[y][x];
                    map[y][x] = 0;
                    first_zero++; // 이전에 0이었던 칸 다음칸은 무조건 0임.
                }
            }
        }

        for (int y = 0; y < N ; y++) {
            for (int x = 0 ; x < N - 1 ; x++) {
                if ((map[y][x] != 0) && (map[y][x] == map[y][x+1])) { // 현재위치가 0이 아닐때, 현재위치와 다음인덱스의 숫자가 같으면 더함.
                    map[y][x] += map[y][x+1];
                    map[y][x+1] = 0;
                    x++; // 어차피 다음인덱스는 0이니까 한칸 건너뜀.
                }
            }
        }

        // 0을 미는 로직.
        for (int y = 0 ; y < N ; y++) {
            int first_zero = -1;

            for (int x = 0 ; x < N ; x++) {
                if ((first_zero == -1) && (map[y][x] == 0)) // 이전에 0인 칸이 없었고, 현재가 0이면
                    first_zero = x;
                else if ((first_zero != -1) && (map[y][x] != 0)) { // 이전에 0인칸이 있고, 현재가 0이 아니면
                    map[y][first_zero] = map[y][x];
                    map[y][x] = 0;
                    first_zero++; // 이전에 0이었던 칸 다음칸은 무조건 0임.
                }
            }
        }

        break;
    default:
        break;
    }
}

void moving(int count) {
    if (count == 5) {
        for (int y = 0 ; y < N ; y++) {
            for (int x=0 ; x < N ; x++) {
                if (result < map[y][x]) 
                    result = map[y][x];
            }
        }

        return ;
    }

    for (int idx = 0 ; idx < 4 ; idx++) {
        int temp_map[MAX][MAX] = {0, };

        memcpy(temp_map, map, sizeof(map));

        add(idx);
        moving(count + 1);

        memcpy(map, temp_map, sizeof(map));
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> N;

    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++)
            cin >> map[y][x];
    }

    moving(0);

    cout << result;

    return 0;
}
728x90

댓글