[백준 12100번] 2048 (easy)

난이도: 골드 2

문제 링크: www.acmicpc.net/problem/12100

출처: 삼성 SW역량 테스트

12100번: 2048 (Easy)

백준 12100번: 2048 (easy)

문제 설명이 긴 편이므로, 위 링크에서 직접 읽어 보시는 것을 추천드립니다.

 

잘 알려진 2048이라는 게임을 부분적으로 구현한 후,

최대 5번 움직을 때 얻을 수 있는 가장 큰 값을 출력하는 문제입니다.

'움직임' 이라고 함은 상하좌우 네 방향으로 숫자들을 이동시키는 것을 말하며, 이 때 이동하는 방향 중 값이 같고 아직 합쳐지지 않은 숫자를 만났다면 두 수를 더합니다.

예를 들어 2 2 4 0 8 이라는 숫자가 있다면, 왼쪽으로 한번 이동하면 4 4 8 0 0, 한번 더 이동하면 8 8 0 0 0, 한번 더 이동하면 16 0 0 0 0의 결과를 얻게 됩니다.

 

저는 이렇게 접근했습니다.

기존 배열을 board[i][j]라고 하겠습니다. 

다음과 같은 배열이 입력으로 들어온다고 가정합시다 (문제에서 주어진 테스트케이스를 약간 변형하였습니다).

2	2	4
4	4	4
8	8	8

board[i] = 2, 2, 2가 됩니다.

이제 숫자를 왼쪽으로 모으는 경우, 문제에서 요구하는 조건대로라면 board[0][0]과 board[0][1]의 값이 더해져 board[0][0]에 저장되고, board[0][2]의 값이 board[0][1]로 이동해야 합니다. 이 때 새롭게 board[0][0]에 저장되어 있는 4는 이미 덧셈이 한번 이루어진 결과로써 저장된 값이므로, board[0][2]에 있던 값과 더해지면 안 됩니다.

 

즉, 1회 이동시킴을 왼쪽으로 하였을 때 얻을 결과는 다음과 같습니다.

4	4	0
8	4	0
16	8	0

0은 숫자가 실제로 존재하는 것이 아닌, 빈 칸을 의미합니다.

i = 0일 때를 기준으로 설명하겠습니다.

저는 위 로직을 구현하기 위해 스택과 큐를 사용했습니다.

우선, board[0][j]의 모든 값을 stack s에 역순으로 담습니다. board[0][2], board[0][1], board[0][0]을 순서대로 담으면, 스택은 LIFO 구조이므로, stack s 내의 값은 {2, 2, 4}가 됩니다.

그 다음, board[0][j]의 값을 모두 0으로 설정합니다. 이것은 해당 행의 값을 우선 전부 비웠음을 뜻합니다.

그 후, 다음 과정을 반복합니다.

1. 스택에서 값을 하나 pop 해서 변수 first에 담습니다.
2. 스택의 상태를 확인합니다. 스택이 비었을 경우, first의 값을 queue q에 삽입하고 종료합니다. 스택이 비어있지 않은 경우, 스택에서 값을 하나 pop해서 변수 second에 담습니다.
3. first와 second의 값을 비교해 봅니다. 두 값이 같은 경우, 두 값을 더해서 queue q에 삽입합니다. 같지 않은 경우, first를 q에 삽입하고, second를 s에 삽입합니다.
4. 위 과정을 스택 s가 완전히 비게 될 때까지 반복합니다.

현재 스택 s = {2, 2, 4}, q = {}, board[0] = {0, 0, 0} 입니다.

위 과정을 따라서 진행해 보겠습니다.

 

1. first = 2가 됩니다. 이후 stack.size() == 2이므로, second = 2가 됩니다. first == second 이므로, 둘을 더한 값 4를 q에 삽입합니다.

따라서 s = {4}, q = {4}, board[0] = {0, 0, 0} 입니다.

2. first = 4가 됩니다. 이후 stack.size() == 0이므로, first의 값을 q에 삽입하고 종료합니다.

따라서 s = {}, q = {4, 4}, board[0] = {0, 0, 0} 입니다.

 

이제 계산한 값을 board에 반영해 주면 됩니다.

q의 index를 하나하나 board에 옮겨 주면 됩니다. pseudocode로 나타내면 대략 이렇게 됩니다.

 

j = 0
while q is not empty:
	now = q.top
    q. pop
    board[0][j] = now
    j++

 

q의 크기가 2이므로, 위 loop는 딱 두 번 반복되게 됩니다.

board[0][0] = 4, board[0][1] = 4 가 되어, 최종적으로 q를 비우고 나면 board[0] = {4, 4, 0}이 됩니다.

성공적으로 값을 왼쪽으로 이동시킨 것을 확인할 수 있습니다.

 

위와 같은 접근 방법은 j의 segmentation error도 걱정하지 않아도 됩니다.

덧셈이 한 번도 이루어지지 않아 queue의 크기가 최대가 되는 최악의 경우를 고려해 보겠습니다.

행렬 board의 크기가 5*5이고, board[0] = {2, 4, 8, 16, 32}라고 가정합시다.

이때 stack s = {2, 4, 8, 16, 32}가 되고, stack을 비우면서 덧셈이 한 번도 이루어지지 않기 때문에 queue q = {2, 4, 8, 16, 32}가 됩니다. 

즉 q의 크기 <= board의 크기 가 되며, 최악의 경우에 등호가 성립합니다.

따라서 board의 범위를 벗어나는 index를 접근하는 경우는 없습니다.

 

위 문제의 경우 시뮬레이션 및 구현의 성질도 포함하고 있습니다.

정확히는 각 값이 이동하는 점은 시뮬레이션, 이를 통해 가능한 경우의 수를 완전 탐색하는 것은 구현에 속한다고 할 수 있습니다.

또, 각 방향에 따라, 총 5회 이동할 때까지 탐색을 해야 하기 때문에, depth가 5일 때까지 탐색하는 DFS에 포함된다고도 할 수 있습니다.

다만 각 방향 (상하좌우) 모두 코드를 따로 써야 하는데, 기본적인 로직은 같지만 세세한 인덱스만 다르고, 또 필연적으로 코드가 매우 길어지기 때문에 오타 등이 생겨도 찾아내기 정말 어렵습니다.

따라서 코딩테스트에서 이런 문제를 마주한다면, 코드를 작성할 때 인덱스값 부분에서 실수를 하지 않도록 아주 주의해야 합니다.

 

	#include <iostream>
	#include <algorithm>
	#include <queue>
	#include <stack>
	using namespace std;
	#define MAX_N 20
	int n;
	int board[MAX_N][MAX_N];
	int maxValue = 0;
	void array_copy(int from[][MAX_N], int to[][MAX_N]) {
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	to[i][j] = from[i][j];
	}
	}
	}
	int get_max_value(int matrix[][MAX_N]) {
	int result = 0;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	result = max(result, matrix[i][j]);
	}
	}
	return result;
	}
	void matrix_shift(int dir, int round, int matrix[][MAX_N]) {
	if (round == 5) return;
	int current_max = 0;
	int board_copy[MAX_N][MAX_N];
	array_copy(matrix, board_copy);
	if (dir == 0) { //왼쪽으로 모으기
	for (int i = 0; i < n; i++) {
	queue<int> q;
	stack<int> s;
	for (int j = n-1; j >= 0; j--) {
	int now = board_copy[i][j];
	if (now != 0) s.push(now);
	}
	for (int j = 0; j < n; j++) {
	board_copy[i][j] = 0;
	}
	while (!s.empty()) {
	int first = s.top();
	s.pop();
	if (s.empty()) {
	q.push(first);
	}
	else {
	int second = s.top();
	s.pop();
	if (first == second)
	q.push(first + second);
	else {
	q.push(first);
	s.push(second);
	}
	}
	}
	int j = 0;
	while (!q.empty()) {
	int now = q.front();
	q.pop();
	board_copy[i][j] = now;
	j++;
	}
	}
	}
	else if (dir == 1) { //오른쪽으로 모으기
	for (int i = 0; i < n; i++) {
	queue<int> q;
	stack<int> s;
	for (int j = 0; j < n; j++) {
	int now = board_copy[i][j];
	if (now != 0) s.push(now);
	}
	for (int j = 0; j < n; j++) {
	board_copy[i][j] = 0;
	}
	while (!s.empty()) {
	int first = s.top();
	s.pop();
	if (s.empty()) {
	q.push(first);
	}
	else {
	int second = s.top();
	s.pop();
	if (first == second)
	q.push(first + second);
	else {
	q.push(first);
	s.push(second);
	}
	}
	}
	int j = n-1;
	while (!q.empty()) {
	int now = q.front();
	q.pop();
	board_copy[i][j] = now;
	j--;
	}
	}
	}
	else if (dir == 2) { //위쪽으로 모으기
	for (int j = 0; j < n; j++) {
	queue<int> q;
	stack<int> s;
	for (int i = n - 1; i >= 0; i--) {
	int now = board_copy[i][j];
	if (now != 0) s.push(now);
	}
	for (int i = 0; i < n; i++) {
	board_copy[i][j] = 0;
	}
	while (!s.empty()) {
	int first = s.top();
	s.pop();
	if (s.empty()) {
	q.push(first);
	}
	else {
	int second = s.top();
	s.pop();
	if (first == second)
	q.push(first + second);
	else {
	q.push(first);
	s.push(second);
	}
	}
	}
	int i = 0;
	while (!q.empty()) {
	int now = q.front();
	q.pop();
	board_copy[i][j] = now;
	i++;
	}
	}
	}
	else if (dir == 3) { //아래쪽으로 모으기
	for (int j = 0; j < n; j++) {
	queue<int> q;
	stack<int> s;
	for (int i = 0; i < n; i++) {
	int now = board_copy[i][j];
	if (now != 0) s.push(now);
	}
	for (int i = 0; i < n; i++) {
	board_copy[i][j] = 0;
	}
	while (!s.empty()) {
	int first = s.top();
	s.pop();
	if (s.empty()) {
	q.push(first);
	}
	else {
	int second = s.top();
	s.pop();
	if (first == second)
	q.push(first + second);
	else {
	q.push(first);
	s.push(second);
	}
	}
	}
	int i = n - 1;
	while (!q.empty()) {
	int now = q.front();
	q.pop();
	board_copy[i][j] = now;
	i--;
	}
	}
	}
	maxValue = max(maxValue, get_max_value(board_copy));
	for (int a = 0; a < 4; a++) {
	matrix_shift(a, round + 1, board_copy);
	}
	}
	int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	int temp;
	cin >> temp;
	board[i][j] = temp;
	}
	}
	for (int i = 0; i < 4; i++) {
	matrix_shift(i, 0, board);
	}
	cout << maxValue;
	return 0;
	}

view raw 12100_2048(easy).cpp hosted with ❤ by GitHub

결과