15) 백준 12100 - 2048 (Easy)

12100번: 2048 (Easy) (acmicpc.net)

12100번: 2048 (Easy)

---

문제는 Easy라고 적혀있지만 나는 Easy하지 않았던 문제...

머리가 안돌아가서 몇 시간 풀어봤지만 정답 보기에는 너무 아쉬워서 계속 시도한 문제... 내가 이겼다. 흐헤헤

#include <bits/stdc++.h>

using namespace std;

int N;
int max_no;

void play(int board[][20], int cnt);

// 1. 위로 
void playUp(int board[][20], int cnt) {
	for(int j = 0; j < N; j++) {
		int position_i = 0;
		int i = 0;
		while(1) {
			if(board[i][j] == 0) {
				i++;
				if(i >= N) break;
				continue;
			}
			board[position_i][j] = board[i][j];
			i++;
			if(i >= N) {
				position_i++;
				break;
			}			
			while(i < N && board[i][j] == 0) {
				i++;
			}
			if(i == N) {
				position_i++;
				break;
			}
			else {
				if(board[i][j] == board[position_i][j]) {
					board[position_i][j] *= 2;
					board[i][j] = 0;
					position_i++;
				}
				else {
					position_i++;
				}
			}
		}
		while(position_i < N) {
			board[position_i][j] = 0;
			position_i++;
		}
	}
    
	play(board, cnt+1);
}

// 2. 아래로 
void playDown(int board[][20], int cnt) {
	for(int j = 0; j < N; j++) {
		int position_i = N-1;
		int i = N-1;
		while(1) {
			if(i < 0) break;
			if(board[i][j] == 0) {
				i--;
				continue;
			}
			board[position_i][j] = board[i][j];
			i--;
			if(i < 0) {
				position_i--;
				break;
			}			
			while(i >= 0 && board[i][j] == 0) {
				i--;
			}
			if(i == -1) {
				position_i--;
				break;
			}
			else {
				if(board[i][j] == board[position_i][j]) {
					board[position_i][j] *= 2;
					board[i][j] = 0;
					position_i--;
				}
				else {
					position_i--;
				}
			}
		}
		
		while(position_i >= 0) {
			board[position_i][j] = 0;
			position_i--;
		}
	}
    
	play(board, cnt+1);
	
}

// 3. 왼쪽으로
void playLeft(int board[][20], int cnt) {
	for(int i = 0; i < N; i++) {
		int position_j = 0;
		int j = 0;
		while(1) {
			if(board[i][j] == 0) {
				j++;
				if(j >= N) break;
				continue;
			}
			board[i][position_j] = board[i][j];
			j++;
			if(j >= N) {
				position_j++;
				break;
			}			
			while(j < N && board[i][j] == 0) {
				j++;
			}
			if(j == N) {
				position_j++;
				break;
			}
			else {
				if(board[i][j] == board[i][position_j]) {
					board[i][position_j] *= 2;
					board[i][j] = 0;
					position_j++;
				}
				else {
					position_j++;
				}
			}
		}
		while(position_j < N) {
			board[i][position_j] = 0;
			position_j++;
		}
	}
	
	play(board, cnt+1);
}

// 4. 오른쪽으로 
void playRight(int board[][20], int cnt) {
	for(int i = 0; i < N; i++) {
		int position_j = N-1;
		int j = N-1;
		while(1) {
			if(j < 0) break;
			if(board[i][j] == 0) {
				j--;
				continue;
			}
			board[i][position_j] = board[i][j];
			j--;
			if(j < 0) {
				position_j--;
				break;
			}			
			while(j >= 0 && board[i][j] == 0) {
				j--;
			}
			if(j == -1) {
				position_j--;
				break;
			}
			else {
				if(board[i][j] == board[i][position_j]) {
					board[i][position_j] *= 2;
					board[i][j] = 0;
					position_j--;
				}
				else {
					position_j--;
				}
			}
		}
		
		while(position_j >= 0) {
			board[i][position_j] = 0;
			position_j--;
		}
	}
	
	play(board, cnt+1);
	
}

void play(int board[][20], int cnt) {
	if(cnt == 6) {
		for(int a = 0; a < N; a++) {
			for(int b = 0; b < N; b++) {
				if(max_no < board[a][b]) max_no = board[a][b];
			}
		}
		return;
	}
	int cpy_board[20][20] = {0, };
	copy(&board[0][0], &board[0][0]+400, &cpy_board[0][0]);
	playUp(board, cnt);
	copy(&cpy_board[0][0], &cpy_board[0][0]+400, &board[0][0]);
	playDown(board, cnt);
	copy(&cpy_board[0][0], &cpy_board[0][0]+400, &board[0][0]);
	playLeft(board, cnt);
	copy(&cpy_board[0][0], &cpy_board[0][0]+400, &board[0][0]);
	playRight(board, cnt);
}

int main(void) {
	int board[20][20] = {0, };
	
	cin >> N;
	max_no = 2;
	
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			cin >> board[i][j];
			if(max_no < board[i][j])
				max_no = board[i][j];
		}
	}
	play(board, 1);
	
	cout << max_no;
}

길어보이지만 사실 위 / 아래 / 좌 / 우 4개가 같은 코드다.

 

위로 올리는 경우 방법은 다음과 같다.

1. 가장 위 부터 차례로 찾는데 0이 아닌 곳을 찾는다.

2. 0이 아닌 수를 찾았으면 position_i를 사용해서 미리 땡겨둔다. 

3. 다음 수가 0 제외하고 같다면 position_i위치에 있는 수를 2배 해주고 땡겨온 곳은 0으로 바꿔준다.

4. 다르다면 position_i를 하나 증가시켜주고 다음으로 넘어간다. (2번의 경우 때문에 여기서 당길 필요는 없다.)

5. 다 끝났으면 position_i 다음 수부터 전부 0으로 채워준다. (빈칸이라는 뜻)

 

헷갈렸던 점은

왜 playUP 후에 playDown으로 넘어가는데 board가 playUp에서 바꾼 값이 들어갔는지 몰랐다.

 - copy를 사용해서 원래 board 값을 붙여넣어줬다.

 

이걸 찾느라 시간이 꽤 걸렸다...ㅠㅠ

그러다가 4방향 한번에 체크하기 위해서 테스트를 하는데 발견했다.

아마 한방향씩 계속 체크 했으면 못찾았을지도...

 

2차 배열의 copy는 잘 모르고 있었는데 기억해두면 요긴하게 쓰일 것 같다.

죠 으 다 ! ! !