삼성 코딩테스트 기출_(백준)2048(Easy)

난이도  ★★☆

 

문제출처

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

12100번: 2048 (Easy)

포인트(짜면서 내가 실수했던 부분들 위주로)

1. '최대 5번'

나는 5번 모두 움직인 후 max값을 구했다. 그런데 문제 조건은 5번 움직인 후에 최댓값을 구하는 것이 아니라 최대 5번까지 돌리고 그 전에라도 최댓값을 찾기만 하면 되는 것이었다.

 

2. 재귀 호출 끝나고 map의 임시 저장배열인 temp를 한 단계 전으로 돌리기

이 부분은 급하게 짜느라고 temp와 temp2를 남발하게 되었다. 처음에 temp와 map 두 가지로만 구성했고 둘 다 전역으로 선언했었는데, 이렇게 할 경우 recursive함수가 수행되고 나서 리턴되었을 때 temp는 한 단계 전으로 돌아가지 않는다. 따라서 급한대로 temp2를 만들어, temp를 temp2에 옮겨놓고 temp로 recursive를 돌린 후, 다시 호출이 끝난 후 temp에 다시 temp2를 넣는 식으로 구성했다.

(함수 더러움 주의)

 

3. move함수 구현

함수 구현 시 예외 상황이 발생하지 않도록 꼼꼼히 구현해야 하는데, 네 방향 복붙하다가 몇 가지 실수를 하는 바람에 시간을 낭비했다. (주의)

 

정답코드

#include <iostream>
using namespace std;

int N;
int map[25][25];
int maximum = 0;
int ans = 0;

void move(int dir, int temp[25][25]) {
	switch (dir) {
	case 1://상
		for (int j = 0; j < N; j++) {//각 열에 대하여
			int curIndex = 0;//맨 첫 행부터 채워 나간다
			for (int i = 1; i < N; i++) {//1부터 시작함 주의
				if (temp[i][j] == 0)continue;//현재 보는 값이 0이면 pass
				if (temp[curIndex][j]!=0) {//갱신되지 않은 제일 위에 있는 값이 0이 아닌 경우
					if (temp[curIndex][j] == temp[i][j]) {//현재 보는 값이랑 위 값이 같으면
						temp[curIndex++][j] = 2 * temp[i][j];//위 값에 곱하기 2 해주고
						temp[i][j] = 0;//현재 값은 없앤다
					}
					else {//두 갑이 다르면
						temp[++curIndex][j] = temp[i][j];//위 값의 바로 밑 행에 현재 보는 값을 쭉 올려주고
						if (curIndex != i)temp[i][j] = 0;//현재 보는 자리는 0으로 바꿔준다(단, 현재 자리가 위 자리랑 같으면 바꾸지 않음)
					}
				}
				else {//갱신되지 않은 값 중 가장 위에 있는 값이 0일 경우에는
					temp[curIndex][j] = temp[i][j];//현재 값을 그 자리로 쭉 올려준다.
					temp[i][j] = 0;//현재 위치는 0으로 바뀐다.
				}
			}
		}
		break;
	case 2://하
		for (int j = 0; j < N; j++) {
			int curIndex = N-1;
			for (int i = N-2; i >= 0; i--) {
				if (temp[i][j] == 0)continue;
				if (temp[curIndex][j] != 0) {
					if (temp[curIndex][j] == temp[i][j]) {
						temp[curIndex--][j] = 2 * temp[i][j];
						temp[i][j] = 0;
					}
					else {
						temp[--curIndex][j] = temp[i][j];
						if (curIndex != i)temp[i][j] = 0;
					}
				}
				else {
					temp[curIndex][j] = temp[i][j];
					temp[i][j] = 0;
				}
			}
		}
		break;
	case 3://좌
		for (int i = 0; i < N; i++) {
			int curIndex = 0;
			for (int j = 1; j < N; j++) {
				if (temp[i][j] == 0)continue;
				if (temp[i][curIndex] != 0) {
					if (temp[i][curIndex] == temp[i][j]) {
						temp[i][curIndex++] = 2 * temp[i][j];
						temp[i][j] = 0;
					}
					else {
						temp[i][++curIndex] = temp[i][j];
						if (curIndex != j)temp[i][j] = 0;
					}
				}
				else {
					temp[i][curIndex] = temp[i][j];
					temp[i][j] = 0;
				}
			}
		}
		break;
	case 4://우
		for (int i = 0; i < N; i++) {
			int curIndex = N - 1;
			for (int j = N - 2; j >= 0; j--) {
				if (temp[i][j] == 0)continue;
				if (temp[i][curIndex] != 0) {
					if (temp[i][curIndex] == temp[i][j]) {
						temp[i][curIndex--] = 2 * temp[i][j];
						temp[i][j] = 0;
					}
					else {
						temp[i][--curIndex] = temp[i][j];
						if (curIndex != j)temp[i][j] = 0;
					}
				}
				else {
					temp[i][curIndex] = temp[i][j];
					temp[i][j] = 0;
				}
			}
		}
		break;
	}
}

void check(int temp[25][25]) {//맥시멈 값 체크
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (maximum < temp[i][j])maximum = temp[i][j];
		}
	}
	ans = maximum;
}

void recursive(int currentTurn, int temp[25][25], int dir) { //현재 몇 번 움직였는지, 현재 상태, 움직일 방향
	int temp2[25][25];//지역변수로서의 현재 상태
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			temp2[i][j] = temp[i][j];
		}
	}//저장해놓는다

	check(temp);//맥시멈 값 체크

	if (currentTurn > 5) {
		return;
	}//다섯 번 초과하면 리턴
	
	if (currentTurn == 1) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				temp[i][j] = map[i][j];
			}
		}
	}//1회차 움직일 때에는 초기 map 상태로 초기화된 상태 필요

	for (int i = 1; i <= 4; i++) {
		move(i, temp);		
		recursive(currentTurn + 1, temp, i);
		for (int i = 0; i < N; i++) {//한 단계 전으로 돌려놔 준다.
			for (int j = 0; j < N; j++) {
				temp[i][j] = temp2[i][j];
			}
		}
	}
	

	return;
}

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	
	recursive(1, map, 1);

	cout << ans << '\n';

	return 0;
}