백준 12100번 _2048(Easy)

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

12100번: 2048 (Easy)

 

풀이방법

 이 문제의 시간은 어떻게 풀던 충분하다고 생각되어 방향을 왼쪽, 위, 오른쪽, 아래를 각각 1,2 3 4로 두고 board판 자체를 회전시키는 방법으로 풀었다.

 

 위 그림을 보면 더 이해가 쉬울것이다.

 

 그외 주의사항은

첫번째, 수가 합해지는 동작을 할때 이미 합쳐진 부분은 합쳐지지 않는 것

 

두번째, 시간 줄인다고 괜히 연속되는 방향으로의 수행을 막는것을 하지 말것

 원래 dfs문제의 시간을 줄이기 위해 똑같은 방향을 연속으로 수행하지 않기 위해 제외하는 경우가 있는데 이 문제는 이미 합쳐진 부분은 합쳐지지 않는 것 이 특성 때문에 연속으로 수행도 허락해야 한다. ( 내가 이 부분때문에 약 30분간 모든 반례를 다 넣어봤다. ㅡㅡ )

---

전체코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>>originalBoard;
int N;

void Input()
{
	cin >> N;
	originalBoard.resize(N + 2);
	for (int i = 0; i < N; i++)
		originalBoard[i].resize(N + 2);

	int value;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> value;
			originalBoard[i][j] = value;
		}
	}
}

void printBoard(const vector<vector<int>>& board)
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << board[i][j] << ' ';
		}
		cout << endl;
	}
}

void CW(vector<vector<int>>& board)
{
	vector<vector<int>> changeBoard = board;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			changeBoard[i][j] = board[N - 1 - j][i];
		}
	}
	board = move(changeBoard);
}

void moveOne(vector<vector<int>>& board, int dir)
{
	if (dir == 2)
		CW(board);
	else if (dir == 3)
	{
		CW(board);
		CW(board);
	}
	else if (dir == 4)
	{
		CW(board);
		CW(board);
		CW(board);
	}

	for (int i = 0; i < N; i++)
	{
		vector<int> tmp;
		tmp.resize(N + 2);
		//움직일 방향으로 밀어서 계산할 벡터에 넣기
		int idx = 0;
		for (int j = 0; j < N; j++)
		{
			if (board[i][j] != 0)
			{
				tmp[idx] = board[i][j];
				board[i][j] = 0;
				idx++;
			}
		}
		//계산
		for (int j = 0; j < N - 1; j++)
		{
			if (tmp[j] == tmp[j + 1])
			{
				tmp[j] += tmp[j + 1];
				tmp[j + 1] = 0;
			}
		}
		//계산 값을 보드에 다시 넣기
		idx = 0;
		for (int j = 0; j < N; j++)
		{
			if (tmp[j] != 0)
			{
				board[i][idx] = tmp[j];
				idx++;
			}
		}
	}
	if (dir == 2)
	{
		CW(board);
		CW(board);
		CW(board);
	}
	else if (dir == 3)
	{
		CW(board);
		CW(board);
	}
	else if (dir == 4)
	{
		CW(board);
	}
}

int countMaxValueInBoard(const vector<vector<int>>& board)
{
	int maxValue = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (board[i][j] > maxValue)
				maxValue = board[i][j];
	return maxValue;
}

int answer;
void dfs(vector<vector<int>>board, int cnt, int dir)
{
	if (cnt > 5)
	{
		answer = max(answer, countMaxValueInBoard(board));
		return;
	}
	moveOne(board, dir);

	for (int i = 1; i <= 4; i++)
	{
		dfs(board, cnt + 1, i);
	}
}

int main()
{
	Input();
	for (int i = 1; i <= 4; i++)
		dfs(originalBoard, 1, i);

	cout << answer;

	return 0;
}

---

후기

 이 문제를 첫번째 풀때는 공부가 된다기 보단 풀이에 급급했는데 두번째로 푸니 마음에 여유가 생겨 여러방면으로 시간을 줄이고, 코딩량을 줄이는 방향 등등을 생각하고 풀어 오히려 빠른시간안에 풀수 있었다.

 

 하지만 이런문제 2문제는 4시간이 주어지면 몰라도 3시간은 좀 빠듯한거 같다ㅠ