1. 문제

12100번: 2048 (Easy)

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

www.acmicpc.net

2048 (Easy)

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

512 MB

30030

7439

4332

23.341%

문제

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번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

출력

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

예제 입력 1 복사

3 2 2 2 4 4 4 8 8 8

예제 출력 1 복사

2. 소스코드

1회차 - 20/03/12

- 지금(20/05/07) 이 소스를 다시 보니......

- 정답(int val)은 왜 계속 갱신했을까? 2048(HARD)를 위한 큰 그림이였을까?.... 배열은 왜 복사했다, 지웠다.... right, left, up, down....

- queue를 이용해 직관적으로 간단히 구현한건 좋은 생각인 것 같다.

- 백트래킹 없음.

#include <cstdio>
#include <queue>
#include <string.h>

#pragma warning(disable :4996)

using namespace std;

int map[20][20];
int n, ans = 0;
queue <int > que;

int Left(int arr[][20]) {
	int max = 0;	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j]) {
				que.push(arr[i][j]);
				arr[i][j] = 0;
			}
		}
		int index = 0;
		while (!que.empty()) {
			int temp;
			temp = que.front(); que.pop();
			if (!que.empty()) {
				if (temp == que.front()) {
					temp *= 2;
					que.pop();
				}
			}
			if (temp > max) max = temp;
			arr[i][index] = temp;
			index++;
		}
	}
	return max;
}

int Right(int arr[][20]) {
	int max = 0;
	for (int i = 0; i < n; i++) {
		for (int j = n - 1; j >= 0; j--) {
			if (arr[i][j]) {
				que.push(arr[i][j]);
				arr[i][j] = 0;
			}
		}
		int index = n - 1;
		while (!que.empty()) {
			int temp;
			temp = que.front(); que.pop();
			if (!que.empty()) {
				if (temp == que.front()) {
					temp *= 2;
					que.pop();
				}
			}
			if (temp > max) max = temp;
			arr[i][index] = temp;
			index--;
		}
	}
	return max;
}

int Up(int arr[][20]) {
	int max = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[j][i]) {
				que.push(arr[j][i]);
				arr[j][i] = 0;
			}
		}
		int index = 0;
		while (!que.empty()) {
			int temp;
			temp = que.front(); que.pop();
			if (!que.empty()) {
				if (temp == que.front()) {
					temp *= 2;
					que.pop();
				}
			}
			if (temp > max) max = temp;
			arr[index][i] = temp;
			index++;
		}
	}
	return max;
}

int Down(int arr[][20]) {
	int max = 0;
	for (int i = 0; i < n; i++) {
		for (int j = n - 1; j >= 0; j--) {
			if (arr[j][i]) {
				que.push(arr[j][i]);
				arr[j][i] = 0;
			}
		}
		int index = n - 1;
		while (!que.empty()) {
			int temp;
			temp = que.front(); que.pop();
			if (!que.empty()) {
				if (temp == que.front()) {
					temp *= 2;
					que.pop();
				}
			}
			if (temp > max) max = temp;
			arr[index][i] = temp;
			index--;
		}
	}
	return max;
}

void dfs(int input[][20], int index) {

	if (index > 5) return;
	int val;
	int copy[20][20];
	/*
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			copy[i][j] = input[i][j];
		}
	}
	*/
	memcpy(copy, input, sizeof(copy));
	
	val = Up(copy);
	if (val > ans) ans = val;
	dfs(copy, index + 1);
	memcpy(copy, input, sizeof(copy));

	val = Down(copy);
	if (val > ans) ans = val;
	dfs(copy, index + 1);
	memcpy(copy, input, sizeof(copy));

	val = Left(copy);
	if (val > ans) ans = val;
	dfs(copy, index + 1);
	memcpy(copy, input, sizeof(copy));

	val = Right(copy);
	if (val > ans) ans = val;
	dfs(copy, index + 1);
	memcpy(copy, input, sizeof(copy));
	
	return;
}
int main() {

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	dfs(map, 1);
	printf("%d\n", ans);
	return 0;
}

2회차 - 20/05/07

- queue를 이용하지 않고 구현.

- 백트래킹. 1) 의미없는 경우(움직여도 변화가 없는 경우) 제외, 2) 정답이 될 수 없는 경우 제외

- 4방향을 따로 만들지 않고, 배열을 회전함. 단, 2048(HARD)에서는 하드코딩에 비해 속도가 유의미하게 느리다.

- 2048 (HARD)도 AC가능한 소스.

#pragma warning (disable : 4996)
#include <cstdio>
#include <memory.h>
#include <algorithm>
#define MAX 20
#define TRY 5
using namespace std;

struct Info
{
    int map[MAX][MAX];
    int depth = 0, maxBlock = 0;
    bool changed;

}info;
int n, ans;

Info turn90(Info info) {
    int temp[MAX][MAX];
    memcpy(temp, info.map, sizeof(temp));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            info.map[j][n - 1 - i] = temp[i][j];
        }
    }
    return info;
}

Info move(Info info) {

    bool changed = true;
    for (int i = 0; i < n; ++i) { // <<--- 방향만 생각. 배열을 뒤집을 것.
        int mgIdx = 0, nIdx = 0;
        for (int j = 0; j < n; ++j) {
            //백트래킹을 위해서 최대값 갱신. 합쳐질때 최대값 한번더 갱신.
            if (info.map[i][j] > info.maxBlock) info.maxBlock = info.map[i][j];
            if (j == 0 or info.map[i][j] == 0) continue; // 첫 자리거나 0이면 skip한다.
            if (info.map[i][mgIdx] == info.map[i][j]) {//같은 경우 합침
                info.map[i][mgIdx] *= 2, info.map[i][j] = 0;
                if (info.maxBlock < info.map[i][mgIdx]) info.maxBlock = info.map[i][mgIdx];
                changed = true, ++mgIdx;
            }
            else if (info.map[i][j - 1]) ++mgIdx; // 같지 않고 공백(0)이 없는 경우
            else {// 같지 않고 공백(0)이 있는 경우
                for (nIdx; nIdx < j; ++nIdx) {
                    if (info.map[i][nIdx] == 0) {
                        swap(info.map[i][j], info.map[i][nIdx]); // 빈공간이랑 스왑
                        changed = true; mgIdx = nIdx++; // 다음 합치는 idx은 수를 넣은 공간
                        break;
                    }
                }
            }
        }
    }
    info.changed = changed;
    return info;
}

void dfs(Info info) {

    if (info.depth > TRY - 1) {// 5번 실행된 경우 return;
        ans = info.maxBlock > ans ? info.maxBlock : ans;
        return;
    }
    if (ans and ans >= info.maxBlock * 2 * (TRY - info.depth)) {// 정답이 될 가능성이 없는 경우 return;
        return;
    }
    int cnt = 0;
    for (int i = 0; i < 4; ++i) {
        Info temp = move(info);
        if (temp.changed) {
            temp.depth++;
            dfs(temp);
        }
        else ++cnt;
        info = turn90(info);
    }

    if (cnt == 4) { //예외, 4방향 전부 움직이는게 불가능한 경우. 
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (info.map[i][j] > info.maxBlock) info.maxBlock = info.map[i][j];
            }
        }
        ans = info.maxBlock;
    }
    return;
}


int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &info.map[i][j]);
        }
    }//input end

    dfs(info);
    printf("%d", ans);
    return 0;
}

'알고리즘 > BOJ(백준)' 카테고리의 다른 글

[ 백준-14503번 / ] 로봇 청소기 (삼성SW) (0)	2020.03.13
[ 백준-14502번 / 완전탐색 ] 연구소 (삼성기출) (0)	2020.03.12
[ 백준-14499번 / ] 주사위 굴리기 (삼성기출) (0)	2020.03.10
[ 백준-16235번 / 시뮬레이션 ] 나무 재테크 - (삼성SW) (0)	2020.03.09
[ 백준-13458번 / 구현 ] 시험 감독 (삼성기출) (0)	2020.03.09

뎁꼼 둥지

[ 백준-12100번 / 완전탐색 / 백트래킹 ] 2048(Easy) (삼성기출)

1. 문제

2048 (Easy)

문제

입력

출력

예제 입력 1 복사

예제 출력 1 복사

2. 소스코드

'알고리즘 > BOJ(백준)' 카테고리의 다른 글

티스토리툴바

[ 백준-12100번 / 완전탐색 / 백트래킹 ] 2048(Easy) (삼성기출)

1. 문제

2048 (Easy)

문제

입력

출력

예제 입력 1 복사

예제 출력 1 복사

2. 소스코드

'알고리즘 > BOJ(백준)' 카테고리의 다른 글

관련글

티스토리툴바