[BOJ] 12100 : 2048 (Easy)
풀이
DFS, 반복문
DFS,BFS 아무것도 모를때 6중반복문으로 몇시간꼬박해서 풀었던 문제였다.
(해당코드는 아래에 있다)
DFS배운김에 DFS로 다시 풀어봤다.
게임은 재미있어서 풀때마다 해본다. 2048만들기는 어렵다.
실수할까봐 상세히 주석을 적어두고 풀었다.
cmd에 따라서 바뀌는 부분은 멋지게 함수로 깔끔하게 만드는것에는 실패해서
복사붙여넣기로 꼼꼼하게 수정해줬다.(그래서 코드가 길다)
dfs로 cmd 순열을 만든 다음에 각각 cmd에 맞게
ppap()와 ddang()을 수행한다. 그리고 배열을 뒤져 최대값을 갱신한다.
ppap()는 같은 숫자가 합칠수 있으면 합쳐주는 함수이다.
ddang()은 cmd방향으로 0을 제외한 숫자들을 다밀어주는 함수이다.
코드 DFS
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int arr[21][21];
int backup[21][21];
int n;
//< ^ > v : 0,1,2,3
vector<int> cmd;
int ans;
void ddang(int i,int cmd) {
//왼
if (cmd == 0) {
int p = -1;
int q = 0;
while (q < n) {
if (arr[i][q] == 0) {
if (p == -1) {
p = q;
}
}
else {
if (p != -1) {
arr[i][p] = arr[i][q];
arr[i][q] = 0;
q = p;
p = -1;
}
}
q++;
}
}
//위
if (cmd == 1) {
int p = -1;
int q = 0;
while (q < n) {
if (arr[q][i] == 0) {
if (p == -1) {
p = q;
}
}
else {
if (p != -1) {
arr[p][i] = arr[q][i];
arr[q][i] = 0;
q = p;
p = -1;
}
}
q++;
}
}
//오른
if (cmd == 2) {
int p = -1;
int q = n-1;
while (q >= 0) {
if (arr[i][q] == 0) {
if (p == -1) {
p = q;
}
}
else {
if (p != -1) {
arr[i][p] = arr[i][q];
arr[i][q] = 0;
q = p;
p = -1;
}
}
q--;
}
}
//아래
if (cmd == 3) {
int p = -1;
int q = n-1;
while (q >= 0) {
if (arr[q][i] == 0) {
if (p == -1) {
p = q;
}
}
else {
if (p != -1) {
arr[p][i] = arr[q][i];
arr[q][i] = 0;
q = p;
p = -1;
}
}
q--;
}
}
}
void ppap(int i,int cmd) {
//0이면 넘어가고 0이아닌 다음칸이 같은숫자를 살펴봐야한다.
//또 합쳐지면 안된다.
if (cmd == 0) {
int k = 0;
int p = -1;
while (k < n) {
if (arr[i][k] != 0 && p == -1) {
p = k;
}
else if (arr[i][k] != 0 && arr[i][k]==arr[i][p]) {
arr[i][p] *= 2;
arr[i][k] = 0;
p = -1;
}
else if (arr[i][k] != 0) {
p = k;
}
k++;
}
}
if (cmd == 1) {
int k = 0;
int p = -1;
while (k < n) {
if (arr[k][i] != 0 && p == -1) {
p = k;
}
else if (arr[k][i] != 0 && arr[k][i] == arr[p][i]) {
arr[p][i] *= 2;
arr[k][i] = 0;
p = -1;
}
else if (arr[k][i] != 0) {
p = k;
}
k++;
}
}
if (cmd == 2) {
int k = n-1;
int p = -1;
while (k >= 0) {
if (arr[i][k] != 0 && p == -1) {
p = k;
}
else if (arr[i][k] != 0 && arr[i][k] == arr[i][p]) {
arr[i][p] *= 2;
arr[i][k] = 0;
p = -1;
}
else if (arr[i][k] != 0) {
p = k;
}
k--;
}
}
if (cmd == 3) {
int k = n-1;
int p = -1;
while (k >= 0) {
if (arr[k][i] != 0 && p == -1) {
p = k;
}
else if (arr[k][i] != 0 && arr[k][i] == arr[p][i]) {
arr[p][i] *= 2;
arr[k][i] = 0;
p = -1;
}
else if (arr[k][i] != 0) {
p = k;
}
k--;
}
}
}
void move(int i) {
//< ^ > v : 0,1,2,3
if (cmd[i] == 0) {
for (int k = 0; k < n; k++) {
//왼쪽부터 '0이 아닌' 다음칸(오른쪽)이 같은숫자인지 살핀다.
//같은 숫자이면 해당칸x2하고 다음칸0으로한다.
ppap(k, 0);
//왼쪽부터 0인부분을 떙겨준다.
ddang(k,0);
}
}
else if (cmd[i] == 1) {
for (int k = 0; k < n; k++) {
//위쪽부터 '0이 아닌' 다음칸(아래쪽)이 같은숫자인지 살핀다.
//같은 숫자이면 해당칸x2하고 다음칸0으로한다.
ppap(k, 1);
//위쪽부터 0인부분을 떙겨준다.
ddang(k, 1);
}
}
else if (cmd[i] == 2) {
for (int k = 0; k < n; k++) {
//오른쪽부터 '0이 아닌' 다음칸(왼쪽)이 같은숫자인지 살핀다.
//같은 숫자이면 해당칸x2하고 다음칸0으로한다.
ppap(k, 2);
//오른쪽부터 0인부분을 떙겨준다.
ddang(k, 2);
}
}
else if (cmd[i] == 3) {
for (int k = 0; k < n; k++) {
//아래쪽부터 '0이 아닌' 다음칸(위쪽)이 같은숫자인지 살핀다.
//같은 숫자이면 해당칸x2하고 다음칸0으로한다.
ppap(k, 3);
//아래쪽부터 0인부분을 떙겨준다.
ddang(k, 3);
}
}
}
void go(int cnt) {
if (cnt == 5) {
//arr를 원래상태로 rollback
memcpy(arr, backup, sizeof(arr));
//명령어대로 움직여봄
for (int i = 0; i < 5; i++) {
move(i);
}
//최대값 탐색
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j]>ans) {
ans = arr[i][j];
}
}
}
return;
}
for (int i = 0; i < 4; i++) {
cmd.push_back(i);
go(cnt + 1);
cmd.pop_back();
}
}
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 >> arr[i][j];
backup[i][j] = arr[i][j];
}
}
go(0);
cout << ans;
return 0;
}
코드 반복문
#include <stdio.h>
#include <string.h>
int input[21][21] = { 0 };
int arr[21][21] = { 0 };
int flag[21][21] = { 0 };
int main() {
int n;
int i, j, k;
int cnt = 0;
scanf("%d", &n);//n:1~20 ->arr:0~19
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &input[i][j]);
}
}
int max = 0;
int keyArr[5] = { 0 };
int a, b, c, d, e,f;
for (a = 0; a < 4; a++) {
keyArr[0] = a;
for (b = 0; b < 4; b++) {
keyArr[1] = b;
for (c = 0; c < 4; c++) {
keyArr[2] = c;
for (d = 0; d < 4; d++) {
keyArr[3] = d;
for (e = 0; e < 4; e++) {
keyArr[4] = e;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
arr[i][j] = input[i][j];
}
}
for (f = 0; f < 5; f++) {
//////////////////////////////////////////////////
memset(flag, 0, sizeof(flag));
/*printf("a:%d b:%d c:%d d:%d e:%d\n", a, b, c, d, e);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}*/
//left
if (keyArr[f] == 0) {
for (k = 0; k < n; k++) {
cnt = 0;
for (j = 0; j < n - 1; j++) {
for (i = 0; i < n; i++) {
if (arr[i][j] != 0 && arr[i][j] == arr[i][j + 1] && (flag[i][j] == 0 && flag[i][j + 1] == 0)) {
arr[i][j] = arr[i][j] << 1;
flag[i][j] = 1;
arr[i][j + 1] = 0;
}
else if (arr[i][j + 1] != 0 && arr[i][j] == 0) {
//교환후, 플래그도 같이 위쪽으로 올라감
arr[i][j] = arr[i][j + 1];
arr[i][j + 1] = 0;
if (flag[i][j + 1] == 1)
flag[i][j] = 1;
flag[i + 1][j] = 0;
}
else {
cnt++;
}
}
}
if (cnt == (n - 1)*n)
break;
}
}
//right
else if (keyArr[f] == 1) {
for (k = 0; k < n; k++) {
cnt = 0;
for (j = n - 2; j >= 0; j--) {
for (i = 0; i < n; i++) {
if (arr[i][j + 1] != 0 && arr[i][j] == arr[i][j + 1] && (flag[i][j] == 0 && flag[i][j + 1] == 0)) {
arr[i][j + 1] = arr[i][j + 1] << 1;
flag[i][j + 1] = 1;
arr[i][j] = 0;
}
else if (arr[i][j] != 0 && arr[i][j + 1] == 0) {
arr[i][j + 1] = arr[i][j];
arr[i][j] = 0;
if (flag[i][j] == 1) {
flag[i][j + 1] = 1;
flag[i][j] = 0;
}
}
else {
cnt++;
}
}
}
if (cnt == (n - 1)*n)
break;
}
}
//up
else if (keyArr[f] == 2) {
for (k = 0; k < n; k++) {
cnt = 0;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n; j++) {
if (arr[i][j] != 0 && arr[i][j] == arr[i + 1][j] && (flag[i][j] == 0 && flag[i + 1][j] == 0)) {
arr[i][j] = arr[i][j] << 1;
flag[i][j] = 1;
arr[i + 1][j] = 0;
}
else if (arr[i + 1][j] != 0 && arr[i][j] == 0) {
//교환후, 플래그도 같이 위쪽으로 올라감
arr[i][j] = arr[i + 1][j];
arr[i + 1][j] = 0;
if (flag[i + 1][j] == 1) {
flag[i][j] = 1;
flag[i + 1][j] = 0;
}
}
else {
cnt++;
}
}
}
if (cnt == (n - 1)*n)
break;
}
}
//down
else if (keyArr[f] == 3) {
for (k = 0; k < n; k++) {
cnt = 0;
for (i = n - 2; i >= 0; i--) {
for (j = 0; j < n; j++) {
if (arr[i + 1][j] != 0 && arr[i][j] == arr[i + 1][j] && (flag[i][j] == 0 && flag[i + 1][j] == 0)) {
arr[i + 1][j] = arr[i + 1][j] << 1;
flag[i + 1][j] = 1;
arr[i][j] = 0;
}
else if (arr[i][j] != 0 && arr[i + 1][j] == 0) {
arr[i + 1][j] = arr[i][j];
arr[i][j] = 0;
if (flag[i][j] == 1) {
flag[i + 1][j] = 1;
flag[i][j] = 0;
}
}
else {
cnt++;
}
}
}
if (cnt == (n - 1)*n)
break;
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (max < arr[i][j]) {
max = arr[i][j];
}
}
}
//////////////////////////////////////////////
}
}
}
}
}
}
printf("%d", max);
return 0;
}
Written on April 9, 2019