[C++] G1 백준 12100 - 2048 (Easy) (클래스5)

1. 문제 링크

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

소요 시간 : 3시간 30분

시도 횟수 : 3

 

2. 문제 설명

난이도 : G1

사용 알고리즘 : 구현, DFS, 투포인터

2048 게임판을 5번 움직였을 때 만들 수 있는 가장 큰 수를 찾는 문제

 

3. 풀이 방식 및 해결

굉장히 디테일한 로직 설명과 5번의 움직임이라는 말을 보고 DFS 기반 구현하면 되겠다 싶었다.

다만 노트 없이 풀었더니 놓친 부분이 꽤나 많았다는 점,,변수가 무척 많았다는 점...

중간에 코드가 복잡해서 한 번 갈아 엎었는데도 꽤나 많은 시간이 들었다.

 

주요 로직은

상/하/좌/우로 움직일 때 각각 up/down, left/right로 투포인터를 이용했고, 각 칸들이 0일때와 그렇지 않을 때를 구분하며 로직을 작성했다.

다른 사람들의 풀이를 찾아보니 방향은 위쪽으로 움직이는 것으로만 통일하고 90, 180, 270도 돌려주는 로직을 구현하는 방식도 있는 듯 하다!

 

#include<iostream>
#include<algorithm>

using namespace std;

int n;
int field[20][20];
int ans = 0;

void dfs(int cnt, int dir, int map[][20]) {//dir : 0 1 2 3 (시계방향 상 우 하 좌)
	if (cnt > 4) return;

	if (dir == 0) {//위
		for (int i = 0; i < n; i++) {
			int up = 0;
			for (int down = 1; down < n; down++) {//합쳐질 때
				if (map[up][i] == 0) {//0이면
					if (map[down][i] == 0) continue;//다음거 보거나
					else {//옮겨와
						map[up][i] = map[down][i];
						map[down][i] = 0;
					}
				}
				else {//0이 아니면
					if (map[up][i] == map[down][i]) {//같으면 합치기
						map[up][i] *= 2;
						map[down][i] = 0;
						if (map[up][i] > ans) ans = map[up][i];
						up++;
					}
					else if (map[down][i] == 0) continue;
					else {//4 2 혹은 4 0 2
						if (up + 1 == down) up++;
						else {
							up++;
							map[up][i] = map[down][i];
							map[down][i] = 0;
						}
					}
				}
			}
		}
	}
	else if (dir == 1) {//오른쪽
		for (int i = 0; i < n; i++) {
			int right = n-1;
			for (int left = right-1; left>=0; left--) {//합쳐질 때
				if (map[i][right] == 0) {//0이면
					if (map[i][left] == 0) continue;//다음거 보거나
					else {//옮겨와
						map[i][right] = map[i][left];
						map[i][left] = 0;
					}
				}
				else {//0이 아니면
					if (map[i][right] == map[i][left]) {//같으면 합치기
						map[i][right] *= 2;
						map[i][left] = 0;
						if (map[i][right] > ans) ans = map[i][right];
						right--;
					}
					else if (map[i][left] == 0) continue;
					else {//4 2 혹은 4 0 2
						if (left + 1 == right) right--;
						else {
							right--;
							map[i][right] = map[i][left];
							map[i][left] = 0;
						}
					}
				}
			}
		}
	}
	else if (dir == 2) {//아래
		for (int i = 0; i < n; i++) {
			int down = n-1;
			for (int up = down-1; up >=0; up--) {
				if (map[down][i] == 0) {//0이면
					if (map[up][i] == 0) continue;//다음거 보거나
					else {//옮겨와
						map[down][i] = map[up][i];
						map[up][i] = 0;
					}
				}
				else {//0이 아니면
					if (map[down][i] == map[up][i]) {//같으면 합치기
						map[down][i] *= 2;
						map[up][i] = 0;
						if (map[down][i] > ans) ans = map[down][i];
						down--;
					}
					else if (map[up][i] == 0) continue;
					else {//4 2 혹은 4 0 2
						if (up + 1 == down) down--;
						else {
							down--;
							map[down][i] = map[up][i];
							map[up][i] = 0;
						}
					}
				}
			}
		}
	}
	else {//왼쪽
		for (int i = 0; i < n; i++) {
			int left = 0;
			for (int right = 1; right < n; right++) {
				if(map[i][left]==0) {//0이면
					if (map[i][right] == 0) continue;//다음거 보거나
					else {//옮겨와
						map[i][left] = map[i][right];
						map[i][right] = 0;
					}
				}
				else {//0이 아니면
					if (map[i][left] == map[i][right]) {//같으면 합치기
						map[i][left] *= 2;
						map[i][right] = 0;
						if (map[i][left] > ans) ans = map[i][left];
						left++;
					}
					else if (map[i][right] == 0) continue;
					else {//4 2 혹은 4 0 2
						if (left + 1 == right) left++;
						else {
							left++;
							map[i][left] = map[i][right];
							map[i][right] = 0;
						}
					}
				}
			}
		}
	}

	//다음 dfs 실행
	int tmpmap[20][20];
	copy(&map[0][0], &map[0][0] + 400, &tmpmap[0][0]);
	
	for (int i = 0; i < 4; i++) {
		dfs(cnt + 1, i, map);
		copy(&tmpmap[0][0], &tmpmap[0][0] + 400, &map[0][0]);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> field[i][j];
			if (field[i][j] > ans) ans = field[i][j];
		}
	}

	int tmpmap[20][20];
	copy(&field[0][0], &field[0][0] + 400, &tmpmap[0][0]);

	for (int i = 0; i < 4; i++) {
		dfs(0, i, field);
		copy(&tmpmap[0][0], &tmpmap[0][0] + 400, &field[0][0]);
	}
	cout << ans;
}

 

 

<오늘의 TMI>
2048..한때 굉장히 히트했던 게임이죠 중학생 때였나?
간단하지만 중독성 있는 숫자게임
학창시절 굉장히 열심히 했고 4X4에서 32768인가 65536까진 만들었는데 ㅋㅋ오랜만에 다시 해보고 싶은데 중독될까봐 못하겠음