[BOJ/Gold 5] 백준 23796 2,147,483,648 게임(C++)

문제 링크

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

 

문제

호준이는 2048 게임을 발전시킨 2,147,483,648 게임을 하고 있다.

2,147,483,648 게임은 8×8 크기의 게임판에서 키보드의 방향키를 통해 2^k (1 ≤ k ≤ 30)꼴에 해당하는 정수가 쓰여 있는 타일들을 움직이며 2,147,483,648( = 2^31)을 만드는 것이 목적인 게임이다. 이 게임은 방향키가 눌렸을 때 다음과 같은 규칙으로 진행된다.

1. 눌린 방향키와 같은 방향으로 타일들을 벽 끝까지 밀어 넣는다.
2. 만약 밀어넣는 방향으로 같은 수가 두 타일 연속해서 존재한다면 그 두 타일을 합친다. 만약 세 타일 이상 연속해있다면 방향키가 가리키는 쪽의 벽에 가까운 쪽부터 두 개씩 합쳐진다.
3. 한 번의 방향키 입력에 한 타일이 두 번 이상 합쳐지는 경우는 없다.

예를 들어 현재 게임판이 다음 그림과 같은 상태라고 하자.

여기에서 왼쪽 방향키(L)가 눌렸을 때 다음 그림과 같이 게임판이 바뀐다.

호준이는 행동 취소 기능도 없는 이 게임을 며칠 동안 밤새 하다 보니 이젠 키 하나를 눌러도 게임판이 어떻게 바뀔지 전혀 감을 잡지 못하는 상태에 이르렀다. 호준이를 위해 현재의 게임판과 누를 방향키를 주면 위 규칙대로 진행했을 때의 게임판을 출력하는 프로그램을 작성하자.

입력

8줄에 걸쳐 각 줄마다 8개의 정수가 공백으로 구분되어 들어온다. 0은 빈 칸을 의미하고, 나머지 정수는 2^k (1 ≤ k ≤ 30)의 꼴을 만족한다.

9번째 줄에는 U, D, L, R 중 하나의 알파벳이 들어온다. 각각 위쪽, 아래쪽, 왼쪽, 오른쪽 방향키를 누른다는 의미이다.

출력

주어진 게임판에서 방향키를 눌렀을 때의 결과물을 출력하라. 입력으로 주어지는 게임판과 같은 형태로 출력한다.

예제 입력 1

4 0 0 8 0 0 0 0
0 0 0 0 0 0 0 0
0 0 2 2 0 0 0 0
2 0 2 8 0 0 0 0
0 0 0 0 0 16 32 64
0 0 2 8 0 16 32 64
0 0 0 0 0 128 256 512
2 0 2 0 0 1024 2048 4096
U

예제 출력 1

4 0 4 8 0 32 64 128
4 0 4 2 0 128 256 512
0 0 0 16 0 1024 2048 4096
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

예제 입력 2

16 2 4 8 0 0 0 0
2 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
16 32 8192 16384 32768 65536 0 0
L

예제 출력 2

16 2 4 8 0 0 0 0
2 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
16 32 8192 16384 32768 65536 0 0

알고리즘 분류

• 구현

풀이

정해진 방향대로 숫자들을 옮기면 된다.
여기서 최대 2,147,483,648까지 나올 수 있는데, 이 숫자는 int32 정수형의 범위를 넘어선 숫자이므로 int 자료형이 아닌 long long 자료형으로 변수를 선언해야 한다.
숫자를 옮기는 방식은 다음과 같다.

• 현재 칸의 숫자를 새로운 변수를 선언한 후 초기화하여 저장한다.
• 숫자를 새로운 변수에 저장했으니 우선 현재 칸의 숫자를 0으로 만든다.
• 현재 칸의 숫자가 이동한 후 놓이는 위치를 찾는다.
• 놓이는 위치가 경계와 맞닿은 칸이라면 그냥 그 자리에 놓는다.
• 놓이는 위치가 경계와 맞닿은 칸이 아니라면 그 다음 칸의 숫자와 비교해서, 숫자가 일치하면 그 다음 칸의 숫자를 2배로 증가시키고, 일치하지 않는다면 놓이는 위치에 숫자를 놓는다.

모든 작업이 끝나면 마지막으로 게임판의 변화한 상태를 띄어쓰기와 개행으로 구분하여 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 8
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
LL MAP[MAX][MAX];
bool Visited[MAX][MAX];
char Cmd;

void input() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            cin >> MAP[i][j];
        }
    }
    cin >> Cmd;
}

void settings() {
    if (Cmd == 'U') {
        for (int j = 0; j < MAX; j++) {
            for (int i = 1; i < MAX; i++) {
                LL Now = MAP[i][j];
                int Index = i;
                while (1) {
                    if (Index == 0) {
                        break;
                    }
                    else {
                        if (MAP[Index - 1][j] == 0) {
                            Index--;
                        }
                        else {
                            break;
                        }
                    }
                };
                if (Index == 0) {
                    MAP[i][j] = 0;
                    MAP[Index][j] = Now;
                }
                else {
                    if (MAP[Index - 1][j] == Now) {
                        if (!Visited[Index - 1][j]) {
                            Visited[Index - 1][j] = true;
                            Now *= 2;
                            MAP[i][j] = 0;
                            MAP[Index - 1][j] = Now;
                        }
                        else {
                            MAP[i][j] = 0;
                            MAP[Index][j] = Now;
                        }
                    }
                    else {
                        MAP[i][j] = 0;
                        MAP[Index][j] = Now;
                    }
                }
            } 
        }
    }
    else if (Cmd == 'D') {
        for (int j = 0; j < MAX; j++) {
            for (int i = MAX - 2; i >= 0; i--) {
                LL Now = MAP[i][j];
                int Index = i;
                while (1) {
                    if (Index == MAX - 1) {
                        break;
                    }
                    else {
                        if (MAP[Index + 1][j] == 0) {
                            Index++;
                        }
                        else {
                            break;
                        }
                    }
                };
                if (Index == MAX - 1) {
                    MAP[i][j] = 0;
                    MAP[Index][j] = Now;
                }
                else {
                    if (MAP[Index + 1][j] == Now) {
                        if (!Visited[Index + 1][j]) {
                            Visited[Index + 1][j] = true;
                            Now *= 2;
                            MAP[i][j] = 0;
                            MAP[Index + 1][j] = Now;
                        }
                        else {
                            MAP[i][j] = 0;
                            MAP[Index][j] = Now;
                        }
                    }
                    else {
                        MAP[i][j] = 0;
                        MAP[Index][j] = Now;
                    }
                }
            } 
        }
    }
    else if (Cmd == 'L') {
        for (int i = 0; i < MAX; i++) {
            for (int j = 1; j < MAX; j++) {
                LL Now = MAP[i][j];
                int Index = j;
                while (1) {
                    if (Index == 0) {
                        break;
                    }
                    else {
                        if (MAP[i][Index - 1] == 0) {
                            Index--;
                        }
                        else {
                            break;
                        }
                    }
                };
                if (Index == 0) {
                    MAP[i][j] = 0;
                    MAP[i][Index] = Now;
                }
                else {
                    if (MAP[i][Index - 1] == Now) {
                        if (!Visited[i][Index - 1]) {
                            Visited[i][Index - 1] = true;
                            Now *= 2;
                            MAP[i][j] = 0;
                            MAP[i][Index - 1] = Now;
                        }
                        else {
                            MAP[i][j] = 0;
                            MAP[i][Index] = Now;
                        }
                    }
                    else {
                        MAP[i][j] = 0;
                        MAP[i][Index] = Now;
                    }
                }
            }
        }
    }
    else if (Cmd == 'R') {
        for (int i = 0; i < MAX; i++) {
            for (int j = MAX - 2; j >= 0; j--) {
                LL Now = MAP[i][j];
                int Index = j;
                while (1) {
                    if (Index == MAX - 1) {
                        break;
                    }
                    else {
                        if (MAP[i][Index + 1] == 0) {
                            Index++;
                        }
                        else {
                            break;
                        }
                    }
                };
                if (Index == MAX - 1) {
                    MAP[i][j] = 0;
                    MAP[i][Index] = Now;
                }
                else {
                    if (MAP[i][Index + 1] == Now) {
                        if (!Visited[i][Index + 1]) {
                            Visited[i][Index + 1] = true;
                            Now *= 2;
                            MAP[i][j] = 0;
                            MAP[i][Index + 1] = Now;
                        }
                        else {
                            MAP[i][j] = 0;
                            MAP[i][Index] = Now;
                        }
                    }
                    else {
                        MAP[i][j] = 0;
                        MAP[i][Index] = Now;
                    }
                }
            }
        }
    }
}

void find_Answer() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            cout << MAP[i][j] << " ";
        }
        cout << "\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}