[C++] 백준 12100 2048(Easy)

문제 링크

---

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

12100번: 2048 (Easy)

 

접근 방법

---

(1) 문제에서 제시하는 2048게임은 한 턴에 동, 서, 남, 북 4방향 중 1방향으로 이동이 가능하고, 최대 5번 이동이 가능하므로, 4^5 = 1024가지의 경우의 수가 존재한다. 1024번의 경우의 수를 탐색하기 위해 백트래킹(DFS)기법을 사용하여 최댓값을 도출하면 된다.

 

(2) 어떤 방향으로 이동을 시킬 때, 3가지 단계로 구분하였다. 

 1. 한쪽으로 모든 숫자를 몰아넣는다.(예시: 서쪽 방향)

 2. 이동시킨 방향(서쪽)의 끝을 기준으로 시작하여 인접한 수가 같으면 합친다.

 3. 다시 이동시킨 방향으로 몰아 넣는다.

이런 과정을 거치면 한 쪽 방향에 대한 이동이 끝난다.

 

(3) (2)의 과정에 대한 소스 코드

// 서쪽으로 이동 시킬때의 예시
for (int i = 0; i < n; i++) {
	int zerocnt = 0; //빈 공간의 갯수를 새기 위한 변수 -> 수를 몇칸 이동시킬지 결정
    //1번 과정
	for (int j = n - 1; j >= 0; j--) {
		if (map[i][j] == 0) { //빈 공간일 때
			zerocnt++;
		}
		else { //빈 공간이 아닐 때
			if (zerocnt != 0) {
				map[i][j + zerocnt] = map[i][j];
				map[i][j] = 0;
			}
		}
	}
    // 2번 과정
	for (int j = n - 1; j > 0; j--) {
		if (map[i][j - 1] == map[i][j]) { //인접한 숫자가 같다면
			map[i][j] *= 2; 
			map[i][j - 1] = 0;
		}
	}
    // 3번 과정
	zerocnt = 0;
	for (int j = n - 1; j >= 0; j--) {
		if (map[i][j] == 0) {
			zerocnt++;
		}
		else {
			if (zerocnt != 0) {
				map[i][j + zerocnt] = map[i][j];
				map[i][j] = 0;
			}
		}
	}
}

 

소스 코드

---

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, result;

vector<vector<int>> move(int dir, vector<vector<int>> map) { //0 북 1 서 2 동 3 남
	if (dir == 0) {
		for (int j = 0; j < n; j++) {
			int zerocnt = 0;
			for (int i = 0; i < n; i++) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i - zerocnt][j] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
			for (int i = 0; i < n - 1; i++) {
				if (map[i][j] == map[i + 1][j]) {
					map[i][j] += map[i + 1][j];
					map[i + 1][j] = 0;
				}
			}
			zerocnt = 0;
			for (int i = 0; i < n; i++) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i - zerocnt][j] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
		}
	}
	if (dir == 1) {
		for (int i = 0; i < n; i++) {
			int zerocnt = 0;
			for (int j = n - 1; j >= 0; j--) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i][j + zerocnt] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
			for (int j = n - 1; j > 0; j--) {
				if (map[i][j - 1] == map[i][j]) {
					map[i][j] *= 2;
					map[i][j - 1] = 0;
				}
			}
			zerocnt = 0;
			for (int j = n - 1; j >= 0; j--) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i][j + zerocnt] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
		}
	}
	if (dir == 2) {
		for (int j = 0; j < n; j++) {
			int zerocnt = 0;
			for (int i = n - 1; i >= 0; i--) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i + zerocnt][j] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
			for (int i = n - 1; i > 0; i--) {
				if (map[i][j] == map[i - 1][j]) {
					map[i][j] *= 2;
					map[i - 1][j] = 0;
				}
			}
			zerocnt = 0;
			for (int i = n - 1; i >= 0; i--) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i + zerocnt][j] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
		}
	}
	if (dir == 3) {
		for (int i = 0; i < n; i++) {
			int zerocnt = 0;
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i][j - zerocnt] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
			for (int j = 0; j < n - 1; j++) {
				if (map[i][j] == map[i][j + 1]) {
					map[i][j] *= 2;
					map[i][j + 1] = 0;
				}
			}
			zerocnt = 0;
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i][j - zerocnt] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
		}
	}
	return map;
}


int find_max(vector<vector<int>> map) {
	int maximum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			maximum = max(maximum, map[i][j]);
		}
	}
	return maximum;
}

void solve(int cnt, vector<vector<int>> &map) {
	if (cnt == 5) {
		result = max(find_max(map), result);
		return;
	}
	for (int i = 0; i < 4; i++) {
		vector<vector<int>> tmp = map; //이동시키기 전의 상태를 저장
		map = move(i, map);
		solve(cnt + 1, map);
		map = tmp;   //이동시키기 전의 상태로 복구
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	vector<vector<int>> map;
	vector<vector<int>> tmp;

	cin >> n;

	map.resize(n);
	tmp.resize(n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int num;
			cin >> num;
			map[i].push_back(num);
		}
	}
	solve(0, map);
	cout << result;
}

개발 환경 : VS2019

질문, 지적 환영합니다!