[알고리즘] 2048 (Easy)

포인트

1. dfs를 통해 4가지 방향으로 진행한다.

2. 2048에서 구현은 생각보다 까다롭다. 

(맵 입력) -> (재귀를 통한 방향 정하기 중복 순열) ->(2048 로직 구하기) -> (최댓값)

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <iostream>
#include <algorithm>
#include <cstring>

#define MAX 20
using namespace std;

int n, answer;
int map[MAX][MAX];
int cmap[MAX][MAX];
int visited[5];

void moveLeft() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            bool check = false;
            if (cmap[i][j] == 0) {
                int k = j + 1;
                while (k <= n - 1) {
                    if (cmap[i][k] != 0) {
                        check = true;
                        break;
                    }
                    k++;
                }
                if (check == true) {
                    cmap[i][j] = cmap[i][k];
                    cmap[i][k] = 0;
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (cmap[i][j] == cmap[i][j + 1]) {
                cmap[i][j] = cmap[i][j] * 2;
                cmap[i][j + 1] = 0;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            bool check = false;
            if (cmap[i][j] == 0) {
                int k = j + 1;
                while (k <= n - 1) {
                    if (cmap[i][k] != 0) {
                        check = true;
                        break;
                    }
                    k++;
                }
                if (check == true) {
                    cmap[i][j] = cmap[i][k];
                    cmap[i][k] = 0;
                }
            }
        }
    }
}

void moveRight() {
    for (int i = 0; i < n; i++) {
        for (int j = n - 1; j > 0; j--) {
            bool check = false;
            if (cmap[i][j] == 0) {
                int k = j - 1;
                while (k >= 0) {
                    if (cmap[i][k] != 0) {
                        check = true;
                        break;
                    }
                    k--;
                }
                if (check == true) {
                    cmap[i][j] = cmap[i][k];
                    cmap[i][k] = 0;
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = n - 1; j > 0; j--) {
            if (cmap[i][j] == cmap[i][j - 1]) {
                cmap[i][j] = cmap[i][j] * 2;
                cmap[i][j - 1] = 0;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = n - 1; j > 0; j--) {
            bool check = false;
            if (cmap[i][j] == 0) {
                int k = j - 1;
                while (k >= 0) {
                    if (cmap[i][k] != 0) {
                        check = true;
                        break;
                    }
                    k--;
                }
                if (check == true) {
                    cmap[i][j] = cmap[i][k];
                    cmap[i][k] = 0;
                }
            }
        }
    }
}

void moveUp() {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n; j++) {
            bool Check = false;
            if (cmap[i][j] == 0) {
                int k = i + 1;
                while (k <= n - 1) {
                    if (cmap[k][j] != 0) {
                        Check = true;
                        break;
                    }
                    k++;
                }

                if (Check == true) {
                    cmap[i][j] = cmap[k][j];
                    cmap[k][j] = 0;
                }
            }
        }
    }

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n; j++) {
            if (cmap[i][j] == cmap[i + 1][j]) {
                cmap[i][j] = cmap[i][j] * 2;
                cmap[i + 1][j] = 0;
            }
        }
    }

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n; j++) {
            bool Check = false;
            if (cmap[i][j] == 0) {
                int k = i + 1;
                while (k <= n - 1) {
                    if (cmap[k][j] != 0) {
                        Check = true;
                        break;
                    }
                    k++;
                }

                if (Check == true) {
                    cmap[i][j] = cmap[k][j];
                    cmap[k][j] = 0;
                }
            }
        }
    }
}

void moveDown() {
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < n; j++) {
            bool Check = false;
            if (cmap[i][j] == 0) {
                int k = i - 1;
                while (k >= 0) {
                    if (cmap[k][j] != 0) {
                        Check = true;
                        break;
                    }
                    k--;
                }
                if (Check == true) {
                    cmap[i][j] = cmap[k][j];
                    cmap[k][j] = 0;
                }
            }
        }
    }

    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < n; j++) {
            if (cmap[i - 1][j] == cmap[i][j]) {
                cmap[i][j] = cmap[i][j] * 2;
                cmap[i - 1][j] = 0;
            }
        }
    }
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < n; j++) {
            bool Check = false;
            if (cmap[i][j] == 0) {
                int k = i - 1;
                while (k >= 0) {
                    if (cmap[k][j] != 0) {
                        Check = true;
                        break;
                    }
                    k--;
                }
                if (Check == true) {
                    cmap[i][j] = cmap[k][j];
                    cmap[k][j] = 0;
                }
            }
        }
    }
}

int findMax() { // 복사된 맵에서 최댓값을 구해준다 .
    int value = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            value = max(value, cmap[i][j]);
        }
    }

    return value;
}

void game() {
    for (int i = 0; i < 4; i++) {
        if (visited[i] == 0)moveRight();
        else if (visited[i] == 1)moveLeft();
        else if (visited[i] == 2)moveDown();
        else if (visited[i] == 3)moveUp();
    }

    answer = max(answer, findMax());
}

void go(int cnt) { //방향을 정한다. 방향을 정하는 방법은 (1, 2, 3, 4, 5) 를 각 자릿수 마다 반복을 할수 있으며
    //중복 순열을 사용한다.
    if (cnt == 5) {
        memcpy(cmap, map, sizeof(map)); // 맵을 복사한다.
        game();
        return;
    }

    for (int i = 0; i < 4; i++) { // 중복 순열을 구하는 방법
        visited[cnt] = i;
        go(cnt + 1);
    }
}

int main() {

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
    //입력을 받는다.

    go(0);
    cout << answer << '\n';
}

python

from collections import deque
from copy import deepcopy


def get(i: int, j: int) -> None:
	if data[i][j]:  
		q.append(data[i][j])
		data[i][j] = 0  


def merge(x: int, y: int, dx: int, dy: int) -> None:
	while q:
		block = q.popleft()  
		if not data[x][y]:  
			data[x][y] = block
		elif data[x][y] == block: 
			data[x][y] = block * 2  
			x, y = x + dx, y + dy
		else:  
			x, y = x + dx, y + dy
			data[x][y] = block


def move(k: int) -> None:
	if k == 0:  
		for j in range(n):
			for i in range(n):
				get(i, j)
			merge(0, j, 1, 0)
	elif k == 1:  
		for j in range(n):
			for i in range(n - 1, -1, -1):
				get(i, j)
			merge(n - 1, j, -1, 0)
	elif k == 2:
		for i in range(n):
			for j in range(n):
				get(i, j)
			merge(i, 0, 0, 1)  
	else:  
		for i in range(n):
			for j in range(n - 1, -1, -1):
				get(i, j)
			merge(i, n - 1, 0, -1)  


def go(cnt: int) -> None:
	global data, answer
	if cnt == 5:  
		for i in range(n):
			answer = max(answer, max(data[i]))  
		return
	
	cdata = deepcopy(data)
	
	for dir in range(4):  
		move(dir)  
		go(cnt + 1)  
		data = deepcopy(cdata)


n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]
answer, q = 0, deque()

go(0)
print(answer)