백준 12100 - 2048 (Easy)

C++

12100 번 - 2048 (Easy)

문제

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오. 문제 출처

접근 방법

아이디어는 간단하다. 최대 5번의 이동이므로, [상, 하, 좌, 우] 중 하나 씩 골라 블록을 이동시키는 걸 5번 반복하여 나온 결과 값 중 최대 블록의 크기를 갱신하여 답을 구한다.

즉 Brute force의 DFS를 이용하여 전체 블록을 이동 시킬 방향을 구하며 이는,

[상,상,상,상,상]  
[상,상,상,상,하]  
[상,상,상,상,좌]  
[상,상,상,상,우]  
[상,상,상,하,상]  
       ~
[우,우,우,우,우]  

로 모든 경우의 수를 탐색한다. 이는 55555로 총 3,125가지의 테스트 케이스가 나온다.

이후 각 경우마다 주어진 방향대로 블럭을 이동시키고, 합쳐진 블록 중 제일 큰 값을 구하여 갱신한다.

구현

Main()

보드의 크기 N와 게임판의 초기 상태를 2차원 배열 arr에 저장한다.
이후 보드를 직접 움직여 보며 답을 구하므로 초기 상태의 게임판을 저장할 saved 2차원 배열도 함께 저장한다.

DFS()

보드를 움직일 방향을 구하는 메소드다.
방향 순서를 나타 낼 dirc[5]의 배열의 각 인덱스(lv)마다 중복을 허용해, 방향을 정해준다.
각 방향은 [상, 하, 좌, 우]를 [0, 1, 2, 3]으로 표현한다.
만약 lv이 5가 되어 5개의 방향을 정하면 MoveBlock()메소드를 호출하여 게임판을 움직인다.
복귀 후 다시 초기 상태의 게임판으로 만들고, 다음 경우를 탐색한다.

MoveBlock()

dirc[5]에 저장된 방향을 하나씩 확인한다.
각 인덱스마다 저장 된 값에 따라 switch로 방향을 정해준다.

4가지 방향으로 이동하는건 다 비슷하므로, 위쪽으로 이동시키는 것을 기준으로 설명을 하겠습니다.
제가 생각한 방법은 각 점마다 자신에게 합쳐질 수 있는 블럭을 찾아 합치거나, 자리를 교환하는 것으로 생각하였습니다. 4*4의 크기의 판을 기준으로 (0,0)에서 (2,3)까지 탐색을 합니다.
처음 점인 (0,0)에서 합칠 수 있는 블록은 (위쪽으로 이동하므로) (1,0) / (2,0) / (3,0)이 있습니다.
만약 기준 블럭의 값이 0이면, 자신의 아래에서 처음에 만나는 블록과 자리를 교체하며 swap한다.
0이 아니며 2의 배수의 값이면, 자신에 아래에서 처음에 만나는 블록을 비교하여 자신과 같은면 합치고, 다르면 해당 블록에서 다음 블록으로 break를 사용해 넘어간다.

다음과 같은 예시로 설명을 드리면,

제일 먼저 (0,0)에 2의 값이 확인 됐으며, 자신의 밑인 (2,0)의 값이 2인것이 확인 되었다. 따라서,

다음과 같이 (0,0)의 값이 4로 합쳐졌으며, (2,0)에 있던 블록은 0으로 치환된다.

이후 (0,1) -> (0,2) -> (0,3)을 지나 (1,0)으로 온다.
이 위치의 블럭의 값은 0이므로, 자신의 아래에 있는 (3,0)에 있는 값이 확인되어 위치를 바꾼다.

따라서, 다음과 같이 위쪽 방향으로 게임판을 이동 시킨다.

이로써

1. 자신과 같은 블록을 합치고
2. 비어있는 위치의 블록이면 블록을 이동시키며
3. 이미 합쳐져있는 블록이면, 같은 블록을 마주쳐도 합쳐지지 않게 구현한다.

위의 방법으로 [하/ 좌/ 우]의 경우에도 인덱스 값만 바꾸어주어 같은 알고리즘으로 구현가능하다

코드

#include <iostream>
#include <vector>

using namespace std;

int n, arr[20][20], saved[20][20];
int dirc[5], maxNum = 0;

void DFS(int);
void MoveBlock();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	clock_t start, end;

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			saved[i][j] = arr[i][j];
		}
	}

	DFS(0);

	cout << maxNum << "\n";
}

void DFS(int lv) {
	if (lv == 5) {
		MoveBlock();
        // 블록들을 처음 상태로 초기화 한다.
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				arr[i][j] = saved[i][j];
		return;
	}
	for (int i = 0; i < 4; i++) {
		dirc[lv] = i;
		DFS(lv + 1);
	}
}

void MoveBlock() {
	for (int idx = 0; idx < 5; idx++) {
		// DFS로 뽑은 방향을 순서대로 움직인다. 0 ~ 3은 각각 상하좌우
		switch (dirc[idx])
		{
		case 0:     // 위쪽으로
			for (int i = 0; i < n - 1; i++) {	        // 제일 왼쪽 위에서 부터 → 방향으로 탐색한다.
				for (int j = 0; j < n; j++) {
					for (int k = i + 1; k < n; k++) {	// 해당 위치의 밑 블록들을 1자로 하나씩 탐색한다.
						if (arr[i][j] == 0) {		    // 만약 해당 블록이 0이면
							if (arr[k][j] != 0) {	    // 자신의 밑의 블록 중 0이 아닌 블록을 처음 만나면 위치를 교환
								swap(arr[k][j], arr[i][j]);
							}
						}
						else {                          // 해당하는 점이 0이 아니며
							if (arr[k][j] != 0) {	    // 자신의 아래 블럭이 자신과 같은 블럭이면 두개 더하고, 아니면 합칠 수 없으므로 break
								if (arr[k][j] == arr[i][j]) {
									arr[i][j] *= 2;
									arr[k][j] = 0;
								}
								break;
							}
						}
					}
				}
			}
			break;
		case 1:     // 아래쪽으로
			for (int i = n - 1; i >= 1; i--) {          // 블럭을 아래쪽으로 내려보내므로, 7시인 왼쪽 밑에서부터 → 방향으로 탐색한다.
				for (int j = 0; j < n; j++) {
					for (int k = i - 1; k >= 0; k--) {
						if (arr[i][j] == 0) {
							if (arr[k][j] != 0) {
								swap(arr[k][j], arr[i][j]);
							}
						}
						else {
							if (arr[k][j] != 0) {
								if (arr[k][j] == arr[i][j]) {
									arr[i][j] *= 2;
									arr[k][j] = 0;
								}
								break;
							}
						}
					}
				}
			}
			break;
		case 2:     // 왼쪽으로
			for (int i = 0; i < n - 1; i++) {           // 왼쪽 위 0,0에서 시작하여 ↓ 방향으로 내려가며 탐색한다.
				for (int j = 0; j < n; j++) {
					for (int k = i + 1; k < n; k++) {
						if (arr[j][i] == 0) {
							if (arr[j][k] != 0) {
								swap(arr[j][k], arr[j][i]);
							}
						}
						else {
							if (arr[j][k] != 0) {
								if (arr[j][k] == arr[j][i]) {
									arr[j][i] *= 2;
									arr[j][k] = 0;
								}
								break;
							}
						}
					}
				}
			}
			break;
		case 3:     // 오른쪽으로
			for (int i = n - 1; i >= 1; i--) {          
				for (int j = 0; j < n; j++) {
					for (int k = i - 1; k >= 0; k--) {
						if (arr[j][i] == 0) {
							if (arr[j][k] != 0) {
								swap(arr[j][k], arr[j][i]);
							}
						}
						else {
							if (arr[j][k] != 0) {
								if (arr[j][k] == arr[j][i]) {
									arr[j][i] *= 2;
									arr[j][k] = 0;
								}
								break;
							}
						}
					}
				}
			}
			break;
		}
	}
    // 5개의 방향으로 블록을 이동 시킨 뒤, 블록 중 최대 값을 갱신한다.
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			maxNum = arr[i][j] > maxNum ? arr[i][j] : maxNum;
	}
}

후기 및 개선할 점

20퍼대 정답률의 문제라도 혼자 고민하면 된다는 자신감을 얻게해준 문제.