백준 12100 2048(Easy) C 풀이 - DFS

문제를 이해하기에 앞서 2048 (play2048.co) 를 한 번 해보면 좋다. 

설명보다 훨씬 직관적으로 이해하기 편하기 때문.

 

Easy 버전 답게 게임과는 다른 점이 있다.

1. 숫자는 초기 상태에서 추가되지 않는다.

2. 만들 수 있는 최대값만 알면 된다.

 

숫자가 추가되지 않고 움직이는 횟수가 적기 때문에 쉽다고 하는 것 같은데, 충분히 머리를 써야한다.

 

접근 방식은 다음과 같다.

1. 맵이 비교적 작고(20*20)  최대 5회까지만 움직이기 때문에 기껏해야 100만번의 경우를 완전탐색하면 된다.

 

해결 방식은 다음과 같다.

1. 현 상태에서 밀 수 있는 경우(좌우상하 네 가지) 중 하나를 수행한다.(DFS)

2. 최댓값을 갱신할 수 있는지 확인하고, 1번을 반복한다.

3. 5번 바꿀 경우 종료한다.

 

고생한점은 다음과 같다.

1. 블록을 맨 앞에서부터 우선적으로 옮기려다보니 처음 탐색할 위치를 잡는 것이 어려웠다.(scan_y,x 배열)

2. 블록을 옮기고 좌표를 수정할 때 같은 변수를 쓰다보니 의도치 않게 좌표가 움직여 루프가 제대로 돌지 않았다.

3. 기존과 다르게 push 를 할 경우 반대 방향 push를 하여 맵을 원상태로 돌리지 못하기 때문에(비가역적) memcpy로 

임시로 상태를 저장하여 원상복구했다. 이럴 경우 dfs가 깊어지면 사용하기 힘들다.(각 STACK마다 tmp배열 따로 존재하여 메모리 초과가 나올 수도 있다.)

 

개선할 수 있을 것 같은 점은 다음과 같다.

1. 못움직이는 것을 제외한 경우는 가지치기하지 못했다. 중복된 상태를 제어하면 더 효율적으로 바뀔 것 같다.(현재 8ms)

2. 맵이 커지거나 옮기는 횟수가 늘어날 경우 tmp배열로 하기는 무리가 있을 것 같다.(현재 1120KB) 

 

전체 코드

#include <stdio.h>
#include <string.h>
int N;
int Map[21][21];//인풋
int Summed[21][21];//이미 합쳐진 블록인지 체크
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
int Max;//정답

//최대값 구하기
int getMax() {
	int ret = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (ret < Map[i][j]) ret = Map[i][j];
		}
	}
	return ret;
}

//dir = 블록 미는 방향
//scan_y = 순서대로 블럭 탐색
// 시작점 sy,sx를 어떤순으로 탐색해야 하는지 scan_y 와 scan_x 로 결정
//가령 sy=0, sx=0 일 경우 sx+=1 로 탐색하고 ,sy+=1로 탐색한다.
//반대로 sy=N-1, sx= N-1일 경우 sx-=1로 탐색하고, sy-=1 로 탐색한다.
//가장 앞에 있는 블록이 먼저 움직여야 합쳐진 후의 위치를 정하기 편하기 때문이다.
void push(int sy, int sx, int dir) {
	static int scan_y[] = { 1,-1,1,-1 };
	static int scan_x[] = { 1,-1, 1, -1 };
	int y = sy;
	int x = sx;
	//합쳐진 경우는 상태마다 초기화해줘야함
	memset(Summed, 0, sizeof(Summed));
	//모든 블럭 탐색
	for (int i = 0; i < N; i++) {
		x = sx;
		for (int j = 0; j < N; j++) {
			//굳이 ty까지 할 필요 없지만 혹시 몰라서 선언
			int ty = y;
			int tx = x;
			//블럭 하나 옮기기
			while (1) {
				//현재 칸이 빈 블록이라면 아무것도 안함
				if (Map[ty][tx] == 0) break;
				int ny = ty + dy[dir];
				int nx = tx + dx[dir];
				//다음칸이 맵 밖일 경우 못감
				if (ny < 0 || ny >= N || nx < 0 || nx >= N) break;
				//다음칸이 이미 합친 경우 못감
				if (Summed[ny][nx]) break;
				//다음칸이 비었을 경우 옮김
				if (Map[ny][nx] == 0) {
					Map[ny][nx] = Map[ty][tx];
					Map[ty][tx] = 0;
					ty = ny;
					tx = nx;
				}
				//다음칸이 같은 숫자고 합친 적이 없는 블록이면 합치고 정지
				else if (Map[ny][nx] == Map[ty][tx]) {
					Map[ny][nx] = Map[ty][tx] * 2;
					Map[ty][tx] = 0;
					Summed[ny][nx] = 1;
					break;
				}
				//다른 숫자가 나올 경우 멈춤
				else {
					break;
				}
			}
			//다음 탐색 블록 
			x+= scan_x[dir];
		}
		y +=  scan_y[dir];
	}

}

int dfs(int num) {
	//5번 이전 상태는 항상 5번 옮긴 상태보다 같거나 작은 최댓값을 가진다
	//(숫자는 항상 유지되거나 커지기 때문)
	//최대 5번 옮겼다면 최대값 구하기
	if (num == 5) {
		int t = getMax();
		if (Max < t) Max = t;
		return 0;
	}

	int sy = 0, sx = 0;
	for (int i = 0; i < 4; i++) {
		//블록 움직일 위치 i 별로 탐색 시작할 위치 설정
		int tmp[21][21];
		//i=0일 경우( y 방향 -1) 0,0부터 탐색
		switch (i) {
		case 0:
			sy = 0;
			sx = 0;
			break;
		case 1:
			sy = N - 1;
			sx = N-1;
			break;
		case 2:
			sy = 0;
			sx = 0;
			break;
		case 3:
			sy = N-1;
			sx = N - 1;
			break;
		default:
			break;
		}
		//현 상태 저장용 지역 변수 배열 tmp;STACK 마다 별개로 존재
		memcpy(tmp, Map, sizeof(Map));
		//방향대로 블록 모두 밀기
		push(sy, sx, i);
		//상태가 변함이 없다면 탐색 안함
		if (memcmp(tmp, Map, sizeof(tmp)) == 0) {
			memcpy(Map, tmp, sizeof(Map));
			continue;
		}
		//옮겨졌다면 
		dfs(num + 1);
		memcpy(Map, tmp, sizeof(Map));

	}
	return 0;
}

int solve() {
	Max = getMax();
	dfs(0);

	return Max;
}
int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &Map[i][j]);
		}
	}


	int ans = solve();
	printf("%d", ans);
}