[Algorithm][C++] BOJ 12100 2048(Easy)

url: https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

풀이 핵심

1. 완전 탐색 문제 (Bruth Force / Back Tracking)

 

2. map을 반시계 방향으로 (시계 방향인지 반시계 방향인지는 중요하지 않음) 회전시키는 함수와 위로 이동시키는 함수를 구현한다. (상 하 좌 우로 이동시키는 함수를 각각 구현하기는 번거롭기 때문)

 

3. 문제에서 가장 중요한 것은 이동시키는 함수를 어떻게 구현하는 것이냐 이다.

• "이미 합쳐진 숫자이므로 합쳐지면 안 돼!" 를 표시할 수 있는 flag와 이동시켜야 하는 위치를 나타내는 target을 이용했다. 
• flag가 true이면 합쳐질 수 있어라는 뜻이고 false이면 합쳐질 수 없어 라는 뜻이다.
• 따라서 flag가 true이고 현재 이동할 위치에 있는 숫자 (temp[target][c]) 와 이동시켜야 하는 숫자 (map[r][c]) 가 같으면 더해 주는 방식으로 구현했다. (temp[target][c] += map[r][c]) 그리고 더 이상 합쳐지면 안 되므로 flag를 false로 바꿔준다.
• 위의 조건을 만족하지 않으면 target을 증가시키고 이동할 숫자 (map[r][c])를 이동할 위치에 이동시킨다. (temp[++target][c] = map[r][c])

 

4. 재귀 함수 형식의 solve를 통해 완전 탐색할 수 있도록 했다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

int N, ans;

struct BOARD {
	int map[20][20];

	int get_max() { // 최대 구하는 함수
		int ret = 0;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				if (ret < map[r][c]) {
					ret = map[r][c];
				}
			}
		}
		return ret;
	}

	void rotate() { // 90도 회전
		int temp[20][20];
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				temp[r][c] = map[c][N - r - 1];
			}
		}
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				map[r][c] = temp[r][c];
			}
		}
	}

	void up() { // 위로 이동시키는 함수
		int temp[20][20] = { 0, };
		for (int c = 0; c < N; c++) {
			bool flag = false; // 이미 합쳐진 숫자이므로 더하면 안 돼!
			int target = -1; // 숫자가 이동할 위치
			for (int r = 0; r < N; r++) {
				if (map[r][c] == 0) continue; // 이동 시킬 숫자가 0이라면 continue
				/*flag가 true이고 이동할 위치의 숫자가 이동시킬 숫자와 같을 때 더한다.
				여기서 target != -1 은 segmentation fault를 피하기 위해 넣었다*/
				if (flag && target != -1 && temp[target][c] == map[r][c]) {
					temp[target][c] += map[r][c];
					flag = false; // 이제 이 숫자는 더 이상 합쳐질 수 없어!
				}
				// 위 조건이 아니라면
				else {
					temp[++target][c] = map[r][c];
					flag = true; // 합쳐질 수 있어
				}
			}
		}
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				map[r][c] = temp[r][c];
			}
		}
	}
};

void solve(BOARD cur, int cnt) {
	if (cnt == 5) {
		int candi = cur.get_max();
		if (ans < candi) ans = candi;
		return;
	}

	for (int dir = 0; dir < 4; dir++) {
		BOARD next = cur;
		next.up();
		solve(next, cnt + 1);
		cur.rotate();
	}
}

int main() {
	BOARD board;
	scanf("%d", &N);
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			scanf("%d", &board.map[r][c]);
		}
	}
	solve(board, 0);
	printf("%d", ans);
	return 0;
}