[14] 2048(Easy)(12100) C++

<

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	18906	4620	2706	22.930%

문제

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

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

<그림 1>	<그림 2>	<그림 3>

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>	<그림 5>	<그림 6>	<그림 7>

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>	<그림 9>

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>	<그림 11>	<그림 12>	<그림 13>

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

<그림 14>	<그림 15>

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

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

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

제한

 

예제 입력 1

3
2 2 2
4 4 4
8 8 8

예제 출력 1

16

힌트

 

출처

• 문제를 만든 사람: baekjoon
• 문제의 오타를 찾은 사람: doju
• 데이터를 추가한 사람: noorycode

알고리즘 분류

• 브루트 포스

메모

 

메모 작성하기

 

 

 

=====================================================================

시뮬레이션이면서 DFS 문제이다.

DFS가 사용되는 부분은 특정 방향으로 값이 0이 아닐때까지 이동하는 경우에 사용했다.

그리고 transform 배열을 만들어서 합쳐지고나면 값을 1로 변경시켜 해당 trial에 더 이상 합쳐지지않도록 구현했다.

그렇게 매번 TRIAL마다 값을 Update 시켜주고, transform 배열을 초기화해줬다.(합쳐져서 막고있던걸 풀어줘야하니까)

그리고 해당 시도가 끝나면 Max값을 찾았다.

 

BOJ에 테스트 케이스가 하나밖에 없어서 당황스러웠다.....

코드는 다음과 같다.

 

 

소스 보기 테마를 선택해 보세요! 테마 설정

#include<iostream> #include<cstring> using namespace std; int N, arr[25][25], arr2[25][25], transform[25][25]; int cnt, str[6],Max = 0; void make(int num, int idx); int main(void) { cin >> N; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++){ cin >> arr[i][j]; arr2[i][j] = arr[i][j]; } } for (int i = 1; i <= 5; i++){ for (int j = 1; j <= 4; j++) { cnt++; str[cnt] = j; make(i,cnt); str[cnt] = 0; cnt--; } } cout << Max << endl; return 0; } bool check(int x, int y) { if (x >= 1 && x <= N && y >= 1 && y <= N) return true; else return false; } void moveLeft(int oX, int oY,int x,int y) { if (check(x, y)) { if (arr[x][y] == 0){ arr[x][y] = arr[oX][oY]; //cout << "(" << oX << "," << oY << ") value to (" << x << "," << y << ")" << endl; arr[oX][oY] = 0; moveLeft(x, y, x, y - 1); } else{//arr[x][y] != 0 if (transform[x][y] == 0 && (arr[oX][oY] == arr[x][y])){ arr[x][y] += arr[oX][oY]; arr[oX][oY] = 0; transform[oX][oY] = 0; transform[x][y] = 1; } } } } void moveRight(int oX, int oY, int x, int y) { if (check(x, y)) { if (arr[x][y] == 0){ arr[x][y] = arr[oX][oY]; //cout << "(" << oX << "," << oY << ") value to (" << x << "," << y << ")" << endl; arr[oX][oY] = 0; moveRight(x, y, x, y + 1); } else{//arr[x][y] != 0 if (transform[x][y] == 0 && (arr[oX][oY] == arr[x][y])){ arr[x][y] += arr[oX][oY]; arr[oX][oY] = 0; transform[oX][oY] = 0; transform[x][y] = 1; } } } } void moveUp(int oX, int oY, int x, int y) { if (check(x, y)) { if (arr[x][y] == 0){ arr[x][y] = arr[oX][oY]; //cout << "(" << oX << "," << oY << ") value to (" << x << "," << y << ")" << endl; arr[oX][oY] = 0; moveUp(x, y, x - 1, y); } else{//arr[x][y] != 0 if (transform[x][y] == 0 && (arr[oX][oY] == arr[x][y])){ arr[x][y] += arr[oX][oY]; arr[oX][oY] = 0; transform[oX][oY] = 0; transform[x][y] = 1; } } } } void moveDown(int oX, int oY, int x, int y) { if (check(x, y)) { if (arr[x][y] == 0){ arr[x][y] = arr[oX][oY]; //cout << "(" << oX << "," << oY << ") value to (" << x << "," << y << ")" << endl; arr[oX][oY] = 0; moveDown(x, y, x + 1, y); } else{//arr[x][y] != 0 if (transform[x][y] == 0 && (arr[oX][oY] == arr[x][y])){ arr[x][y] += arr[oX][oY]; arr[oX][oY] = 0; transform[oX][oY] = 0; transform[x][y] = 1; } } } } void move(int direction) { if (direction == 1){//left for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (arr[i][j] != 0) moveLeft(i, j, i, j - 1); } } } else if (direction == 2){//right for (int i = 1; i <= N; i++) { for (int j = N; j >= 1; j--) { if (arr[i][j] != 0) moveRight(i, j, i, j + 1); } } } else if (direction == 3){//up for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++){ if (arr[i][j] != 0) moveUp(i, j, i - 1, j); } } } else{//down for (int i = N; i >= 1; i--) { for (int j = 1; j <= N; j++){ if (arr[i][j] != 0) moveDown(i, j, i + 1, j); } } } } void fineMax() { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++){ if (Max < arr[i][j]) Max = arr[i][j]; } } } void copy() { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) arr[i][j] = arr2[i][j]; } } void print() { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) cout << arr[i][j] << ' '; cout << endl; } } void make(int num,int idx) { if (idx == num) { copy(); //cout << "\nTrial Order : "; //for (int i = 1; i <= num; i++) // cout << str[i] << ' '; //cout << endl; for (int i = 1; i <= num; i++){ //cout << "*Direction " << str[i] << endl; move(str[i]); //print(); memset(transform, 0, sizeof(transform)); } fineMax(); //cout << " ==> Max is " << Max << endl; return; } else { for (int i = 1; i <= 4; i++) { cnt++; str[cnt] = i; make(num,cnt); str[cnt] = 0; cnt--; } } }

반응형

저작자표시 비영리 변경금지

'알고리즘( C++ ) > 1. BOJ' 카테고리의 다른 글

[16] 퇴사(14501) C++  (0)	2019.04.11
[15] 로봇청소기(14503) C++  (0)	2019.04.09
[13] 연구소(14502) C++  (0)	2019.04.07
[12] 드래곤 커브(15685) C++  (0)	2019.04.07
[11] 구슬 탈출2(13460) C++  (0)	2019.04.02

'알고리즘( C++ )/1. BOJ' Related Articles

• [16] 퇴사(14501) C++ 2019.04.11
• [15] 로봇청소기(14503) C++ 2019.04.09
• [13] 연구소(14502) C++ 2019.04.07
• [12] 드래곤 커브(15685) C++ 2019.04.07

more

Comments