[백준] 12100번: 2048(Easy)

 

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

문제 이해

아주 배열을 세심하게 다뤄야 하는 문제인데, 심지어 예제가 하나밖에 없다.

그냥 본인이 여러 숫자를 넣어가면서 생각대로 잘 맵이 이동하는지를 살피는 수밖에 없다.

 

일단 처음 문제를 읽으면 최대 5번 이동한다고 했으니 5번의 방향을 정하는 DFS를 돌려야할 것 같다는 생각이 든다.

근데, 최대 5번이니까 1번 움직였을 때 최댓값이 나올 수도 있고 2번 움직였을 때 최댓값이 나올 수도 있고... 그렇다.

그래서 이동 한 번 할 때마다 최댓값을 체크해줘야 한다.

(그냥 더이상 값 변동이 없을 때의 값을 체크해도 될 것 같다.)

 

아무튼 나는 그냥 한번 기울일 때마다 max값을 체크해주긴 했다.

 

DFS()

DFS 재귀파트가 조금 헷갈리는게, 매 단계마다 map을 바꿔주기 때문에 원상복구 시키는 게 좀 헷갈렸다. (사실 내가 코드를 누더기처럼 짜서 그럴 수도 있지만)

void DFS(int cnt) {
	// 종료
	if (cnt == 5) return;
	int tmpmap[MAXN + 1][MAXN + 1];
	memcpy(tmpmap, map, sizeof(map));
	// 재귀
	for (int i = 0; i < 4; i++) {
		if (Move_Blocks(i) == 0) {
			memcpy(map, tmpmap, sizeof(map));
			continue;
		}
		DFS(cnt + 1);
		memcpy(map, tmpmap, sizeof(map));
	}
}

처음에 간과했던 부분은 Move_Blocks(i)==0 일때 그냥 continue를 해줬다는 점이다.

그렇게 하면 같은 단계에서 다른 방향으로 기울일 때, 예를 들어 cnt == 1일 때 위쪽으로 한 번 기울이고, 아래쪽으로 기울일 때, 위쪽으로 기울인 map상태로 넘어가서 문제가 된다. 그래서 continue 전에도 한 번 원래 맵을 복붙해줘야 한다

 

결국 원상복귀가 조금 헷갈렸다고 볼 수 있다.

 

 

네 방향으로 기울이는 과정은 네 방향이 다 비슷하다. 좌표들만 조금 주의해서 주면 되는데, 원리를 상세히 설명하기 위해 왼쪽으로 기울이는 과정을 기준으로 설명한다.

Move_Blocks_Left()

일단 나는 숫자가 같은 애들을 합치고, 그러고서 모든 숫자가 왼쪽으로 쏠릴 수 있게 몰아주는 과정을 거쳤다.

이렇게 하면 한 번 더해진 애는 패스할 수 있다.

근데 방향을 조금 주의해야할 것이, 이 함수는 왼쪽으로 기울이는 거니까 왼쪽 끝부터 시작하고, 오른쪽 기울이는 함수는 오른쪽, 위쪽으로 기울이는 함수는 위쪽에서 시작해야 한다. 일단 그래야 안헷갈리고, 한 번 더한 애를 패스할 수 있다.

이 두 과정은 모두 각 행 별로 수행해준다. 설명은 위의 예시를 보면서 설명한다.

1. 숫자가 같은 애들 합치기

• map[0][0]번엔 2가 있다. 이걸 기준으로 오른쪽으로 가면서 확인한다.
• map[0][1]번은 0이다. 0이면 continue 해서 그 뒤에 숫자들을 확인한다.
• map[0][2] c==2번은 2이다. 기준점이었던 map[0][0]과 같다. 그럼 합칠 수 있다.
• map[0][0] 을 두 배를 해주고, map[0][2]는 지워버린다. 그리고 break해서 이 기준점 (map[0][0])에 대한 탐색을 종료한다
• 그럼 map[0][0]에는 4가 담기고, 기준점은 map[0][1]이 된다. 그럼 이제 map[0][0] 은 이 과정에서 다시 건들지 않게 된다. (== 한 번 합쳐진 애는 같은 과정에서 또 합치지 않는다.)
• 새로운 기준점 map[0][1]에 대해 오른쪽으로 가면서 같은 과정을 밟는다.

• for (int j = 0; j < N-1; j++) {
    for (int k = j + 1; k < N; k++) {
      if (map[i][k] == 0) continue;
      if (map[i][k] != map[i][j]) break;
      map[i][j] += map[i][k];
      map[i][k] = 0;
      moved = 1;
      break;
    }
  }

이렇게 하면 숫자가 같은 애들은 다 왼쪽 기준으로 합쳐진다.

2. 공백 지우기

이제 왼쪽으로 모든 숫자가 기울 수 있도록 한다.

또 다시 기준점 map[0][0]부터 시작한다.

• map[0][0]은 4이다. 0이 아니니 패스한다. (continue)
• map[0][1]은 0이다. 0이니까 뒤에 0이 아닌 숫자가 있으면 swap해준다. 어차피 뒤에 없으니까 패스된다.
• 이렇게 첫 번째 행, 두 번째 행을 처리했다고 치고, 세 번째 행을 살펴보자
• map[2][0]은 0이다. 그럼 오른쪽부터 또 탐색하면서 0이 아닌 값을 찾는다. map[2][1]이 16이다. 그럼 map[2][0]으로 이 값을 옮겨준다. 그럼 16 0 0 이 되었다.
• 다음 기준점 map[2][1]을 잡고 또 map[2][2]부터 살핀다. 더이상 숫자가 없어서 패스된다. 

• // 빈 칸 당긴다
  for (int j = 0; j < N; j++) {
    if (map[i][j] == 0) { 
      for (int k = j + 1; k < N; k++) {
        if (map[i][k] == 0) continue;
        map[i][j] = map[i][k];
        map[i][k] = 0;
        moved = 1;
        break;
    }
  }

이런 식으로 처리하면 왼쪽 정렬을 할 수 있다. 

여기에 moved라는 변수가 있는데, map에 위치 변동이 생기지 않으면 moved가 0으로 유지되고, 더이상 이 맵에 대해 기울이기를 반복해봤자 다른 값이 나오지 않는다는 뜻이다.

int Move_Blocks_Left(void) {
	int max = 0;
	int moved = 0;
	for (int i = 0; i < N; i++) {
		// 합칠 애들을 찾는다
		for (int j = 0; j < N-1; j++) {
			for (int k = j + 1; k < N; k++) {
				if (map[i][k] == 0) continue;
				if (map[i][k] != map[i][j]) break;
				map[i][j] += map[i][k];
				map[i][k] = 0;
				moved = 1;
				break;
			}
		}
		// 빈 칸 당긴다
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 0) { 
				for (int k = j + 1; k < N; k++) {
					if (map[i][k] == 0) continue;
					map[i][j] = map[i][k];
					map[i][k] = 0;
					moved = 1;
					break;
				}
			}
			if (map[i][j] > max) max = map[i][j];
		}
	}
	if (max > ans) ans = max;
	return moved;
}

 

전체 코드

#include <stdio.h>
#include <string.h>
#define MAXN 20
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3

int N;
int map[MAXN+1][MAXN+1];

int sel[5 + 1];
int ans;

int dy[] = { -1, 1, 0, 0 }; // 상하좌우
int dx[] = { 0, 0, -1, 1 }; 

void Get_Input(void) {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
		}
	}
}

int Move_Blocks_Up(void) {
	int moved = 0;
	int max = 0;
	for (int c = 0; c < N; c++) {
		// 합칠 애들을 찾는다
		for (int r = 0; r < N-1; r++) {
			for (int k = r + 1; k < N; k++) {
				if (map[k][c] == 0) continue;
				if (map[k][c] != map[r][c]) break;
				map[r][c] += map[k][c];
				map[k][c] = 0;
				moved = 1;
				break;
			}
		}
		// 빈 칸 당긴다
		for (int r = 0; r < N; r++) {
			if (map[r][c] == 0) {
				for (int k = r + 1; k < N; k++) {
					if (map[k][c] == 0) continue;
					map[r][c] = map[k][c];
					map[k][c] = 0;
					moved = 1;
					break;
				}
			}
			if (map[r][c] > max) max = map[r][c];
		}
	}
	if (max > ans) ans = max;
	return moved;
}

int Move_Blocks_Down(void) {
	int moved = 0;
	int max = 0;
	for (int c = 0; c < N; c++) {
		// 합칠 애들을 찾는다
		for (int r = N-1; r > 0; r--) {
			for (int k = r - 1; k >=0; k--) {
				if (map[k][c] == 0) continue;
				if (map[k][c] != map[r][c]) break;
				map[r][c] += map[k][c];
				map[k][c] = 0;
				moved = 1;
				break;
			}
		}
		// 빈 칸 당긴다
		for (int r = N-1; r >0; r--) {
			if (map[r][c] == 0) {
				for (int k = r - 1; k >= 0; k--) {
					if (map[k][c] == 0) continue;
					map[r][c] = map[k][c];
					map[k][c] = 0;
					moved = 1;
					break;
				}
			}
			if (map[r][c] > max) max = map[r][c];
		}
	}
	if (max > ans) ans = max;
	return moved;
}

int Move_Blocks_Left(void) {
	int max = 0;
	int moved = 0;
	for (int i = 0; i < N; i++) {
		// 합칠 애들을 찾는다
		for (int j = 0; j < N-1; j++) {
			for (int k = j + 1; k < N; k++) {
				if (map[i][k] == 0) continue;
				if (map[i][k] != map[i][j]) break;
				map[i][j] += map[i][k];
				map[i][k] = 0;
				moved = 1;
				break;
			}
		}
		// 빈 칸 당긴다
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 0) { 
				for (int k = j + 1; k < N; k++) {
					if (map[i][k] == 0) continue;
					map[i][j] = map[i][k];
					map[i][k] = 0;
					moved = 1;
					break;
				}
			}
			if (map[i][j] > max) max = map[i][j];
		}
	}
	if (max > ans) ans = max;
	return moved;
}


int Move_Blocks_Right(void) {
	int max = 0;
	int moved = 0;
	for (int i = 0; i < N; i++) { // 행
		// 합칠 애들을 찾는다
		for (int j = N-1; j > 0; j--) {
			for (int k = j-1; k >=0; k--) {
				if (map[i][k] == 0) continue;
				if (map[i][k] != map[i][j]) break;
				map[i][j] += map[i][k];
				map[i][k] = 0;
				moved = 1;
				break;
			}
		}
		// 빈 칸 당긴다
		for (int j = N-1; j >= 0; j--) {
			if (map[i][j] == 0) {
				for (int k = j - 1; k >=0; k--) {
					if (map[i][k] == 0) continue;
					map[i][j] = map[i][k];
					map[i][k] = 0;
					moved = 1;
					break;
				}
			}
			if (map[i][j] > max) max = map[i][j];
		}
	}
	if (max > ans) ans = max;
	return moved;
}

int Move_Blocks(int dir) {
	// map을 dir 방향으로 기울인다
	int res = 0;
	switch (dir) {
	case UP:
		res = Move_Blocks_Up();
		break;
	case DOWN:
		res = Move_Blocks_Down();
		break;
	case LEFT:
		res = Move_Blocks_Left();
		break;
	case RIGHT:
		res = Move_Blocks_Right();
		break;
	}
	return res;
}

void DFS(int cnt) {
	// 종료
	if (cnt == 5) return;
	int tmpmap[MAXN + 1][MAXN + 1];
	memcpy(tmpmap, map, sizeof(map));
	// 재귀
	for (int i = 0; i < 4; i++) {
		if (Move_Blocks(i) == 0) {
			memcpy(map, tmpmap, sizeof(map));
			continue;
		}
		DFS(cnt + 1);
		memcpy(map, tmpmap, sizeof(map));
	}
}

int main(void) {
	Get_Input();
	DFS(0);
	printf("%d", ans);
	return 0;
}