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

728x90

12100번: 2048 (Easy)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2

www.acmicpc.net

문제!

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

유명한 퍼즐게임인 2048 게임 구현 문제입니다!

상하좌우로 블록을 합쳐주거나 이동시키는 게임으로

위 문제에서는 제시 상태에서 5번움직여 최대숫자를 출력해주는 것을 요구하고 있네요...

5번만 움직인다는 점을 보면 이동시켜 주며 DFS로 탐색하고 최댓값을 갱신해 주면 될것 같습니다.

(구현은 다해놓고 이상한데서 헤맸네요..)

그럼 처음부터 천천히 시작해보시죠

일단 입력을 받고 MAP에 저장 후 DFS를 돌려보겠습니다.


int n = 0;
int answer = 0;

int map[21][21]; // 기존
int temp_map[21][21]; // 저장
int way[5]; // 이동 방법

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

	cin >> n;
	answer = 0;

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

		}
	}

	dfs(0);
	cout << answer;

	return 0;

}

DFS에서는 이동할 방향을 선택해서 정해주고 5번의 이동방향(0~4)이 저장되면 MOVE 함수를 돌려주겠습니다.

void dfs(int count) {
	
	if (count == 5) {
		move();
		answer = max(find(), answer);
		
		return;	
	}
	for (int i = 0; i < 4; i++) {//방향을 정리
		way[count] = i;
		dfs(count + 1);
	}

	return;

}

다음은 명령에 따라 이동시켜주는 함수를 만들어줍시다.

void move() {// 이동시킴
	map_save();

	for (int i = 0; i < 5; i++) {
		if (way[i] == 0) {//위
			u_move();
		}
		else if (way[i] == 1) {//아래
			d_move();
		}
		else if (way[i] == 2) {//오
			r_move();
		}
		else {//왼
			l_move();
		}
	}
	
	
}

이동시킬때에는 초기의 MAP을 훼손하지 않기위해 TEMP_MAP에 저장해주고 이걸 사용해줍시다.

void map_save() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			temp_map[i][j] = map[i][j];
		}
	}
}

그리고 각각의 이동함수들....

이건 좀 길어서.....

방향별 이동 방법입니다.

//방향에 따른 리스트 합쳐지는거, 이동 
void u_move() {//위   // 항상 이동하는 방향부터 탐색해야할듯...?
	int memo;
	int check;
	
	for (int j = 0; j < n; j++) {//위에서 부터 탐색
		memo = 0;
		check = 0;
		for (int i = 0; i < n; i++) {
			if (temp_map[i][j] != 0) {//0이 아니면
				if (memo == 0) {//저장된게 없음
					memo = temp_map[i][j];
				}
				else {//저장된게 있고
					if (memo == temp_map[i][j]) {//같다면
						temp_map[check][j] = memo * 2;
						
						temp_map[i][j] = 0;
						memo = 0;
						check += 1;	
					}
					else {//다르면
						temp_map[check][j] = memo;
						memo = temp_map[i][j];
						check += 1;
					}
				}
			}
		}
		temp_map[check][j] = memo;
		for (int i = check+1; i < n; i++) {
			temp_map[i][j] = 0;
		}
	}
}


void d_move() {//아래
	int memo;
	int check;

	for (int j = 0; j < n; j++) {//위에서 부터 탐색
		memo = 0;
		check = n-1;
		for (int i = n-1; i >= 0; i--) {
			if (temp_map[i][j] != 0) {//0이 아니면

				if (memo == 0) {//저장된게 없음
					memo = temp_map[i][j];
				}
				else {//저장된게 있고
					if (memo == temp_map[i][j]) {//같다면
						temp_map[check][j] = memo * 2;
						
						temp_map[i][j] = 0;
						memo = 0;
						check -= 1;

					}
					else {//다르면
						temp_map[check][j] = memo;
						memo = temp_map[i][j];
						check -= 1;
					}
				}
			}
		}
		temp_map[check][j] = memo;
		for (int i = 0; i < check; i++) {
			temp_map[i][j] = 0;
		}
	}
}

void r_move() {//오른
	int memo;
	int check;

	for (int i = 0; i < n; i++) {//위에서 부터 탐색
		memo = 0;
		check = n - 1;
		for (int j = n - 1; j >= 0; j--) {
			if (temp_map[i][j] != 0) {//0이 아니면

				if (memo == 0) {//저장된게 없음
					memo = temp_map[i][j];
				}
				else {//저장된게 있고
					if (memo == temp_map[i][j]) {//같다면
						temp_map[i][check] = memo * 2;

						temp_map[i][j] = 0;
						memo = 0;
						check -= 1;

					}
					else {//다르면
						temp_map[i][check] = memo;
						memo = temp_map[i][j];
						check -= 1;
					}
				}
			}
		}
		temp_map[i][check] = memo;
		for (int j = 0; j < check; j++) {
			temp_map[i][j] = 0;
		}
	}
}


void l_move() {//왼
	int memo;
	int check;

	for (int i = 0; i < n; i++) {//위에서 부터 탐색
		memo = 0;
		check = 0;
		for (int j = 0; j < n; j++) {
			if (temp_map[i][j] != 0) {//0이 아니면
				if (memo == 0) {//저장된게 없음
					memo = temp_map[i][j];
				}
				else {//저장된게 있고
					if (memo == temp_map[i][j]) {//같다면
						temp_map[i][check] = memo * 2;

						temp_map[i][j] = 0;
						memo = 0;
						check += 1;
					}
					else {//다르면
						temp_map[i][check] = memo;
						memo = temp_map[i][j];
						check += 1;
					}
				}
			}
		}
		temp_map[i][check] = memo;
		for (int j = check + 1; j < n; j++) {
			temp_map[i][j] = 0;
		}
	}
}

원리는 한쪽끝에서부터 탐색을 시작해

MEMO에 저장된 값과 비교, 같으면 합쳐주고 아니면 밀어주는 방식으로 구성했습니다.

여기까지 하고 이제 탐색이 종료되면

전체 맵의 최댓값과 ANSWER를 비교 갱신해줍시다.

int find() {//큰수 (모든 칸탐색) 
	int max_ans = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			max_ans = max(max_ans, temp_map[i][j]);
		}
	}
	
	return max_ans;
}

그리고 출력해주면 끝!

ALL

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

using namespace std;

int n = 0;
int answer = 0;

int map[21][21]; // 기존
int temp_map[21][21]; // 저장
int way[5]; // 이동 방법


//방향에 따른 리스트 합쳐지는거, 이동 
void u_move() {//위   // 항상 이동하는 방향부터 탐색해야할듯...?
	int memo;
	int check;
	
	for (int j = 0; j < n; j++) {//위에서 부터 탐색
		memo = 0;
		check = 0;
		for (int i = 0; i < n; i++) {
			if (temp_map[i][j] != 0) {//0이 아니면
				if (memo == 0) {//저장된게 없음
					memo = temp_map[i][j];
				}
				else {//저장된게 있고
					if (memo == temp_map[i][j]) {//같다면
						temp_map[check][j] = memo * 2;
						
						temp_map[i][j] = 0;
						memo = 0;
						check += 1;	
					}
					else {//다르면
						temp_map[check][j] = memo;
						memo = temp_map[i][j];
						check += 1;
					}
				}
			}
		}
		temp_map[check][j] = memo;
		for (int i = check+1; i < n; i++) {
			temp_map[i][j] = 0;
		}
	}
}


void d_move() {//아래
	int memo;
	int check;

	for (int j = 0; j < n; j++) {//위에서 부터 탐색
		memo = 0;
		check = n-1;
		for (int i = n-1; i >= 0; i--) {
			if (temp_map[i][j] != 0) {//0이 아니면

				if (memo == 0) {//저장된게 없음
					memo = temp_map[i][j];
				}
				else {//저장된게 있고
					if (memo == temp_map[i][j]) {//같다면
						temp_map[check][j] = memo * 2;
						
						temp_map[i][j] = 0;
						memo = 0;
						check -= 1;

					}
					else {//다르면
						temp_map[check][j] = memo;
						memo = temp_map[i][j];
						check -= 1;
					}
				}
			}
		}
		temp_map[check][j] = memo;
		for (int i = 0; i < check; i++) {
			temp_map[i][j] = 0;
		}
	}
}

void r_move() {//오른
	int memo;
	int check;

	for (int i = 0; i < n; i++) {//위에서 부터 탐색
		memo = 0;
		check = n - 1;
		for (int j = n - 1; j >= 0; j--) {
			if (temp_map[i][j] != 0) {//0이 아니면

				if (memo == 0) {//저장된게 없음
					memo = temp_map[i][j];
				}
				else {//저장된게 있고
					if (memo == temp_map[i][j]) {//같다면
						temp_map[i][check] = memo * 2;

						temp_map[i][j] = 0;
						memo = 0;
						check -= 1;

					}
					else {//다르면
						temp_map[i][check] = memo;
						memo = temp_map[i][j];
						check -= 1;
					}
				}
			}
		}
		temp_map[i][check] = memo;
		for (int j = 0; j < check; j++) {
			temp_map[i][j] = 0;
		}
	}
}


void l_move() {//왼
	int memo;
	int check;

	for (int i = 0; i < n; i++) {//위에서 부터 탐색
		memo = 0;
		check = 0;
		for (int j = 0; j < n; j++) {
			if (temp_map[i][j] != 0) {//0이 아니면
				if (memo == 0) {//저장된게 없음
					memo = temp_map[i][j];
				}
				else {//저장된게 있고
					if (memo == temp_map[i][j]) {//같다면
						temp_map[i][check] = memo * 2;

						temp_map[i][j] = 0;
						memo = 0;
						check += 1;
					}
					else {//다르면
						temp_map[i][check] = memo;
						memo = temp_map[i][j];
						check += 1;
					}
				}
			}
		}
		temp_map[i][check] = memo;
		for (int j = check + 1; j < n; j++) {
			temp_map[i][j] = 0;
		}
	}
}

void map_save() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			temp_map[i][j] = map[i][j];
		}
	}
}

int find() {//큰수 (모든 칸탐색) 
	int max_ans = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			max_ans = max(max_ans, temp_map[i][j]);
		}
	}
	
	return max_ans;
}

void move() {// 이동시킴
	map_save();

	for (int i = 0; i < 5; i++) {
		if (way[i] == 0) {//위
			u_move();
		}
		else if (way[i] == 1) {//아래
			d_move();
		}
		else if (way[i] == 2) {//오
			r_move();
		}
		else {//왼
			l_move();
		}
	}
}

void dfs(int count) {
	
	if (count == 5) {
		move();
		answer = max(find(), answer);
		
		return;	
	}
	for (int i = 0; i < 4; i++) {//방향을 정리
		way[count] = i;
		dfs(count + 1);
	}

	return;

}

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

	cin >> n;
	answer = 0;

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

		}
	}

	dfs(0);
	cout << answer;

	return 0;

}

틀린점이 있다면 댓 달아주세요!

'코딩테스트!(프로그래머스 & 백준) > 백준 - C++' 카테고리의 다른 글

[ 백준 1167 ] 트리의 지름 (C++) (0)	2023.06.04
[ 백준 1202 ] 보석도둑 (C++) (0)	2023.03.02
[ 백준 16236] 아기 상어(C++) (1)	2022.12.28
[ 백준 3190 ] 뱀 (C++) (0)	2022.12.09
[ 백준 10986] 나머지합 (C++) (0)	2022.11.16