문제

문제 링크

해설

• 어려운 구현문제답게 요구하는 작업이 많습니다.
• 최대 20x20에, 이동은 5번이므로 재귀함수를 사용해서 모든 경우의 수를 탐색하면 시간내에 문제를 풀 수 있을 것 같습니다.
  
• 위, 아래, 오른쪽, 왼쪽 이동 연산은 위와 같이 각 경계선의 끝지점부터 시작해서 반대쪽 경계선까지 한 칸씩 탐색합니다.
• 같은 수를 발견한다면 병합하고, 해당 좌표를 visited[][]로 표시합니다. (중복 병합을 막기 위해서)
• 병합이 불가능하고, 다음 이동할 좌표가 빈칸이라면 이동합니다.
• 이와 같은 연산은 위, 아래, 오른쪽, 왼쪽 4방향으로 구현하면 됩니다.

코드

#include <bits/stdc++.h>
using namespace std;

int N, answer;

vector<vector<int>> moveUp(vector<vector<int>> board) {
	vector<vector<bool>> visited(N, vector<bool>(N, false));
	for (int x = 0; x < N; ++x) {					// 모든 열에 대해
		for (int y = 1; y < N; ++y) {				// 1번 행부터
			if (board[y][x] == 0) continue;			// 빈 칸이면 다음 행 탐색
			int targetY = y;						// 이동할 행 번호 저장
			for (int ny = y - 1; ny >= 0; --ny) {
				if (board[ny][x] == board[y][x] && !visited[ny][x]) {
					board[ny][x] <<= 1;				// 결합할 수 있는 경우 2배로 증가
					board[y][x] = 0;				// 현재 위치(y, x) 초기화
					visited[ny][x] = true;			// 중복 결합 회피 위한 체크
				}
				else if (board[ny][x] == 0) targetY = ny;
				else break;
			}
			if (targetY != y) {
				board[targetY][x] = board[y][x];
				board[y][x] = 0;
			}
		}
	}
	return board;
}
vector<vector<int>> moveDown(vector<vector<int>> board) {
	vector<vector<bool>> visited(N, vector<bool>(N, false));
	for (int x = 0; x < N; ++x) {
		for (int y = N - 2; y >= 0; --y) {
			if (board[y][x] == 0) continue;
			int targetY = y;
			for (int ny = y + 1; ny < N; ++ny) {
				if (board[ny][x] == board[y][x] && !visited[ny][x]) {
					board[ny][x] <<= 1;
					board[y][x] = 0;
					visited[ny][x] = true;
				}
				else if (board[ny][x] == 0) targetY = ny;
				else break;
			}
			if (targetY != y) {
				board[targetY][x] = board[y][x];
				board[y][x] = 0;
			}
		}
	}
	return board;
}
vector<vector<int>> moveLeft(vector<vector<int>> board) {
	vector<vector<bool>> visited(N, vector<bool>(N, false));
	for (int y = 0; y < N; ++y) {
		for (int x = 1; x < N; ++x) {
			if (board[y][x] == 0) continue;
			int targetX = x;
			for (int nx = x - 1; nx >= 0; --nx) {
				if (board[y][nx] == board[y][x] && !visited[y][nx]) {
					board[y][nx] <<= 1;
					board[y][x] = 0;
					visited[y][nx] = true;
				}
				else if (board[y][nx] == 0) targetX = nx;
				else break;
			}
			if (targetX != x) {
				board[y][targetX] = board[y][x];
				board[y][x] = 0;
			}
		}
	}
	return board;
}
vector<vector<int>> moveRight(vector<vector<int>> board) {
	vector<vector<bool>> visited(N, vector<bool>(N, false));
	for (int y = 0; y < N; ++y) {
		for (int x = N - 2; x >= 0; --x) {
			if (board[y][x] == 0) continue;
			int targetX = x;
			for (int nx = x + 1; nx < N; ++nx) {
				if (board[y][nx] == board[y][x] && !visited[y][nx]) {
					board[y][nx] <<= 1;
					board[y][x] = 0;
					visited[y][nx] = true;
				}
				else if (board[y][nx] == 0) targetX = nx;
				else break;
			}
			if (targetX != x) {
				board[y][targetX] = board[y][x];
				board[y][x] = 0;
			}
		}
	}
	return board;
}

void solve(vector<vector<int>> board, int depth) {
	if (depth == 5) {
		int ret = 0;
		for (int y = 0; y < N; ++y)
			for (int x = 0; x < N; ++x)
				ret = max(ret, board[y][x]);
		answer = max(answer, ret);
		return;
	}
	for (int i = 0; i < 4; ++i) {
		if (i == 0)			solve(moveUp(board),	depth + 1);
		else if (i == 1)	solve(moveDown(board),	depth + 1);
		else if (i == 2)	solve(moveLeft(board),	depth + 1);
		else if (i == 3)	solve(moveRight(board),	depth + 1);
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(nullptr);
	cin >> N;
	vector<vector<int>> board(N, vector<int>(N));
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < N; ++x)
			cin >> board[y][x];
	
	solve(board, 0);
	cout << answer;
}

• 지역변수로 2차원 배열 visited[][]를 사용했습니다.
• C++17 기준으로 vector<bool>과 vector<vector<bool>>은 내부적으로 std::bitset을 이용한 메모리 최적화 기법을 사용합니다.
  따라서, 위와 같이 구현해도 성능면에서 오버헤드가 거의 없습니다.

소스코드 링크

결과