[백준][12100] 2048(Easy)

이 포스트는 백준 사이트의 2048(Easy) 문제 풀이입니다.

문제

해결 과정

이 문제는 2048 게임의 규칙을 가져오지만 몇 가지 규칙이 더 추가되었습니다.

• 블록을 이동해도 새로운 블록이 추가되지 않습니다.
• 최대 5번까지 이동할 수 있습니다.

위 조건에 따라 주어진 보드를 5번까지 이동시켜 만들 수 있는 최댓값을 출력하면 됩니다.

먼저, 알고리즘을 선택하기 위해 시간 복잡도를 계산하면 다음과 같습니다.
이동 가능한 모든 경우의 수는 \(5^5 = 3,125\) 이고
이동할 때 마다 최댓값을 갱신해야 하고 \(5^5 \times (20 \times 20) = 3,125 \times 400 = 1,250,000\)
이동에 따른 숫자 병합이 있는지 확인해야 합니다. \(5^5 \times (20 \times 20 + 20 \times 20) = 3,125 \times 800 = 2,500,000\)

\(O(N)\) 의 알고리즘을 선택하여도 제한시간 안에 풀이가 가능하므로,
재귀함수를 이용한 완전 탐색을 사용하였습니다.

숫자를 이동시키면서 병합할 때, Queue 를 사용하여 숫자를 병합한 뒤 갱신하였습니다.

코드 구현

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define ll long long

int N;
int dir_row[4]{1, -1, 0, 0};
int dir_col[4]{0, 0, 1, -1};

void input(vector<vector<ll>>& board);
void solution(vector<vector<ll>> board, ll& answer, int time);
ll find_max(vector<vector<ll>>& board);
vector<vector<ll>> move_block(vector<vector<ll>> board, int dir);
int add_block_score(vector<vector<ll>>& board, queue<ll>& block, 
                    int row, int col, int dir);

int main() {
	vector<vector<ll>> board;
	input(board);

	ll answer = 0;
	solution(board, answer, 0);

	printf("%lld", answer);

	return 0;
}

void input(vector<vector<ll>>& board) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	board.assign(N, vector<ll>(N, 0));
	for(int row = 0; row < N; ++row) {
		for(int col = 0; col < N; ++col) {
			cin >> board[row][col];
		}
	}
}

void solution(vector<vector<ll>> board, ll& answer, int time) {
	answer = max(find_max(board), answer);

	if(time == 5) {
		return;
	}
	
	for(int dir = 0; dir < 4; ++dir) {
		solution(move_block(board, dir), answer, time + 1);
	}
}

ll find_max(vector<vector<ll>>& board) {
	ll MAX = 0;
	for(int row = 0; row < N; ++row) {
		for(int col = 0; col < N; ++col) {
			MAX = max(board[row][col], MAX);
		}
	}
	return MAX;
}

vector<vector<ll>> move_block(vector<vector<ll>> board, int dir) {
	if(dir == 0) {
		for(int col = 0; col < N; ++col) {
			queue<ll> block;
			for (int row = 0; row < N; ++row) {
				if(board[row][col] != 0) {
					block.push(board[row][col]);
				}
			}
			int new_row
                 = add_block_score(board, block, 0, col, dir);
			for (; new_row < N; ++new_row) {
				board[new_row][col] = 0;
			}
		}
	} 
	else if(dir == 1) {
		for(int col = 0; col < N; ++col) {
			queue<ll> block;
			for (int row = N - 1; row >= 0; --row) {
				if(board[row][col] != 0) {
					block.push(board[row][col]);
				}
			}
			int new_row 
                = add_block_score(board, block, N - 1, col, dir);
			for (; new_row >= 0; --new_row) {
				board[new_row][col] = 0;
			}
		}
	}
	else if(dir == 2) {
		for(int row = 0; row < N; ++row) {
			queue<ll> block;
			for (int col = 0; col < N; ++col) {
				if(board[row][col] != 0) {
					block.push(board[row][col]);
				}
			}
			int new_col
                 = add_block_score(board, block, row, 0, dir);
			for (; new_col < N; ++new_col) {
				board[row][new_col] = 0;
			}
		}
	} 
	else if(dir == 3) {
		for(int row = 0; row < N; ++row) {
			queue<ll> block;
			for (int col = N - 1; col >= 0; --col) {
				if(board[row][col] != 0) {
					block.push(board[row][col]);
				}
			}
			int new_col
                 = add_block_score(board, block, row, N - 1, dir);
			for (; new_col >= 0; --new_col) {
				board[row][new_col] = 0;
			}
		}
	}

	return board;
}

int add_block_score(vector<vector<ll>>& board, queue<ll>& block, 
                    int row, int col, int dir) {
	int new_row = row;
	int new_col = col;

	while (false == block.empty()) {
		if (block.size() == 1) {
			board[new_row][new_col] = block.front();
			block.pop();
			
			new_row += dir_row[dir];
			new_col += dir_col[dir];
		} else {
			int curr = block.front();
			block.pop();
			int prev = block.front();
			
			if (curr == prev) {
				board[new_row][new_col] = curr + prev;
				new_row += dir_row[dir];
				new_col += dir_col[dir];
				block.pop();
			} else {
				board[new_row][new_col] = curr;
				new_row += dir_row[dir];
				new_col += dir_col[dir];
				board[new_row][new_col] = prev;
			}
		}
	}

	return (new_row == row ? new_col : new_row);
}

실행 결과