백준 12100번 2048(Easy)

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

12100번: 2048 (Easy)

 

 

 

 

 

<접근방법>

중복순열에 동작구현을 하면 되는 문제입니다.

동작구현이 조금 까다로웠습니다.

4방향에 대한 각각의 동작을 압축하는 것이 힘들었습니다.

얼마나 압축할 것인지와 거기에 따라 달라지는 자료구조와 구현이

직관적으로 머리에 담기는 힘들었습니다.

종이에 풀어쓰는 연습이 더 필요할 거 같습니다.

(일기인줄..)

 

콩밥을 먹으면서 콩을 안먹으려면 콩을 골라내야 합니다

골라내서 접시에 담아야겠죠

 

비유가 허접하긴 한데

필요한 부분만 꺼내서 복잡한 연산을 하려면 구현이 꼬이기 쉽습니다.

그래서 따로 꺼내줘서 연산을 하면 편합니다.

(메모리를 많이 쓸수록 구현이 편해지는 부분이 있는 느낌입니다.)

그래서 저는 기울이면 움직이는 0이 아닌 숫자들을 꺼내고 따로 저장해서 다루었습니다.

 

케이스가 나뉘는 구현 문제는 보통 부분적인 기능들을 묶을 수 있습니다.

그래서 최대한 그런 관점으로 시도하려고 노력했습니다.

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
using namespace std;

int n;
int map[20][20];
int a[5];
int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};
int res = 0;

int cal(int tmap[][20]) {
	int tres = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			tres = max(tres, tmap[i][j]);
		}
	}
	return tres;
}

void dfs(int dep, int tmap[][20]) {
	if (dep == 5) {
		res = max(res, cal(tmap));
		return;
	}

	for (int d = 0; d < 4; d++) {//우 상 좌 하
		int cmap[20][20];

		//역연산을 해주기 위함입니다.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cmap[i][j] = tmap[i][j];
			}
		}

		vector<int> v[20];
		vector <int> s[20];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (d == 1 || d == 3) {//상하
					if (tmap[j][i] == 0) continue;
					v[i].push_back(tmap[j][i]);
				}
				else {//좌우
					if (tmap[i][j] == 0) continue;
					v[i].push_back(tmap[i][j]);
				}
			}
		}

		//우하
		if (d == 0 || d == 3) {
			for (int i = 0; i < n; i++) {
				reverse(v[i].begin(), v[i].end());
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < v[i].size(); j++) {
				if (j + 1 < v[i].size() && v[i][j + 1] == v[i][j]) {
					s[i].push_back(v[i][j] * 2);
					j++;
				}
				else {
					s[i].push_back(v[i][j]);
				}
			}

			for (int j = s[i].size(); j < n; j++) {
				s[i].push_back(0);
			}
		}

		if (d == 0 || d == 3) {
			for (int i = 0; i < n; i++) {
				reverse(s[i].begin(), s[i].end());
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (d == 1 || d == 3) {
					tmap[i][j] = s[j][i];
				}
				else {
					tmap[i][j] = s[i][j];
				}
			}
		}

		dfs(dep+1, tmap);

		//역연산
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				tmap[i][j] = cmap[i][j];
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	dfs(0, map);
	cout << res << '\n';
	return 0;
}

 

 

---

 

 

<느낀 점>

-2중 for문 j, i 바꿔서 탐색

-백트래킹의 매개변수 참조가 필요없는 경우가 많다