백준 12100 - 2048(Easy)

문제링크

• 백준 12100

문제설명

• NxN 크기의 보드 위에 블록들이 있고, 전체 블록을 상하좌우 네 방향 중 하나로 이동시킬 수 있다.
• 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다.
• 똑같은 수가 3개 이상 있는 경우 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 즉, 보드의 끝에서부터 합쳐진다.
• 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하라

입력

• 첫째줄에 보드의 크기 N(20이하)이 주어진다.
• N개의 줄에 게임판의 초기 상태가 주어진다. 0은 빈칸, 이외의 값은 모드 블록(2~1024 에 존재하는 2의 제곱수.. 1, 2, 4, 8, 16, 32, …, 512, 1024)

문제접근방향

• 블록을 이동시키는 로직을 크게 두가지로 나눈다.
• 첫번째, 전체 블록을 이동방향에 맞게 움직이기만 한다.
• 두번째, 끝에 위치한 블록부터 옆 블록과 합쳐질 수 있는지 확인하고, 합쳐질 수 있다면 합친다. 합친 결과와 현재 최댓값을 비교하여 최댓값을 갱신한다.
• 위 두 과정을 5번 반복한다. 이때, 모든 경우의 수로 움직일 수 있도록 재귀적인 구현이 필요하고, 이전 보드 상태로 복귀할 수 있는 로직을 추가한다.
• 각 행 또는 열의 블록을 담는 1차원 배열 org_blocks 을 선언하고, 해당 배열에서 합할 수 있는 블록들을 합하여 나온 최종 블록을 담는 added_blocks 을 선언한다.
• 단, org_blocks 에 들어오는 블록들은 상, 좌 움직임의 경우 보드에서 탐색하고 있는 행 또는 열의 0번 인덱스부터 블록을 담고, 하, 우 움직임의 경우 n-1번 인덱스부터 블록을 담는다.

디버깅 과정

• 문제의 핵심은 상하좌우로 이동한 결과가 올바른지를 확인하는 것이다. 이때, 재귀호출 상에서 디버깅을 위한 출력을 하게 되면 상하좌우 모든 방향에 대해서 올바르게 적용되었는지 파악하기가 어렵다.
• 따라서, 상하좌우 움직임에 대한 로직 구현이 완료되고 나면 그 결과를 확인할 수 있는 디버깅용 함수를 제작하였다.

구현

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void add_block(vector<int>& org_blocks, queue<int>& added_blocks, int& max_val) {
	// add blocks
	for (int i = 0; i < org_blocks.size(); i++) {
		if (i == org_blocks.size() - 1) {
			added_blocks.push(org_blocks[i]);
			break;
		}

		if (org_blocks[i] == org_blocks[i + 1]) {
			org_blocks[i] += org_blocks[i + 1];
			added_blocks.push(org_blocks[i]);
			if (max_val < org_blocks[i]) max_val = org_blocks[i];
			i++;
		}
		else {
			added_blocks.push(org_blocks[i]);
		}
	}
	org_blocks.clear();
}

// 보드 위에 전체 블록을 이동시킨다.
void move_blocks(vector<vector<int>>& board, int dir, int& max_val) {
	int n = board.size();
	vector<vector<int>> nboard(n, vector<int>(n, 0));

	int cnt = 0;
	vector<int> org_blocks;
	queue<int> added_blocks;
	// 상하(0,1)는 각 열에 대해서 블록을 이동시키고, 좌우(2,3)은 각 행에 대해서 블록을 이동시킨다.
	switch (dir) {
	case 0:
		for (int c = 0; c < n; c++) {
			for (int r = 0; r < n; r++) {
				if (board[r][c] != 0)
					org_blocks.push_back(board[r][c]);
			}
			if (org_blocks.empty()) continue;

			add_block(org_blocks, added_blocks, max_val);

			// update nboard
			if (added_blocks.empty()) continue;
			for (int r = 0; r < n; r++) {
				nboard[r][c] = added_blocks.front();
				added_blocks.pop();
				if (added_blocks.empty()) break;
			}
		}
		break;
	case 1:
		for (int c = 0; c < n; c++) {
			for (int r = n-1; r >= 0; r--) {
				if (board[r][c] != 0)
					org_blocks.push_back(board[r][c]);
			}
			if (org_blocks.empty()) continue;

			add_block(org_blocks, added_blocks, max_val);

			// update nboard
			if (added_blocks.empty()) continue;
			for (int r = n - 1; r >= 0; r--) {
				nboard[r][c] = added_blocks.front();
				added_blocks.pop();
				if (added_blocks.empty()) break;
			}
		}
		break;
	case 2:
		for (int r = 0; r < n; r++) {
			for (int c = 0; c < n; c++) {
				if (board[r][c] != 0)
					org_blocks.push_back(board[r][c]);
			}
			if (org_blocks.empty()) continue;

			add_block(org_blocks, added_blocks, max_val);

			// update nboard
			if (added_blocks.empty()) continue;
			for (int c = 0; c < n; c++) {
				nboard[r][c] = added_blocks.front();
				added_blocks.pop();
				if (added_blocks.empty()) break;
			}
		}
		break;
	case 3:
		for (int r = 0; r < n; r++) {
			for (int c = n-1; c >= 0; c--) {
				if (board[r][c] != 0)
					org_blocks.push_back(board[r][c]);
			}
			if (org_blocks.empty()) continue;

			add_block(org_blocks, added_blocks, max_val);

			// update nboard
			if (added_blocks.empty()) continue;
			for (int c = n - 1; c >= 0; c--) {
				nboard[r][c] = added_blocks.front();
				added_blocks.pop();
				if (added_blocks.empty()) break;
			}
		}
		break;
	}
	board = nboard;
}

void print_board(vector<vector<int>>& board, int dir) {
	int n = board.size();

	cout << "dir: " << dir << endl;
	cout << "----------------------------\n";
	for (int r = 0; r < n; r++) {
		for (int c = 0; c < n; c++)
			cout << board[r][c] << " ";
		cout << endl;
	}
	cout << endl;
}

// Debugging
void check_move(vector<vector<int>>& board) {
	vector<vector<int>> cur_board = board;
	int tmp_val = 0;
	move_blocks(board, 0, tmp_val);
	print_board(board, 0);

	board = cur_board;
	move_blocks(board, 1, tmp_val);
	print_board(board, 1);

	board = cur_board;
	move_blocks(board, 2, tmp_val);
	print_board(board, 2);

	board = cur_board;
	move_blocks(board, 3, tmp_val);
	print_board(board, 3);
}

void play_game(vector<vector<int>>& board, int& max_val, int n, int cnt) {
	// 기저사례: 보드를 5번 움직인 경우
	if (cnt == 5) return;

	// dir: 상(0), 하(1), 좌(2), 우(3)
	for (int dir = 0; dir < 4; dir++) {
		vector<vector<int>> cur_board = board;
		move_blocks(board, dir, max_val);
		play_game(board, max_val, n, cnt + 1);
		board = cur_board;
	}
}


int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<vector<int>> board(n, vector<int>(n, 0));
	int max_val = 0;
	for (int r = 0; r < n; r++) {
		for (int c = 0; c < n; c++) {
			cin >> board[r][c];
			if (max_val < board[r][c])
				max_val = board[r][c];
		}
	}

	play_game(board, max_val, n, 0);
	cout << max_val << endl;

	// check_move(board);
	return 0;
}

구현(updated)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> AddEle(vector<int> arr, int& ans){
    vector<int> ret;
    for(int i=0; i<arr.size()-1; i++){
        if(arr[i]==arr[i+1]){ 
            if(ans<arr[i]+arr[i+1])
                ans = arr[i]+arr[i+1];
            ret.push_back(arr[i]+arr[i+1]);
            i++;
        }
        else
            ret.push_back(arr[i]);
        if(i==arr.size()-2)
            ret.push_back(arr[i+1]);
    }

    return ret;
}

void MoveUp(vector<vector<int>>& board, int& ans){
    vector<int> arr;
    int n = board.size();
    for(int c=0; c<n; c++){
        for(int r=0; r<n; r++){
            if(board[r][c]==0) continue;
            arr.push_back(board[r][c]);
            board[r][c]=0;
        }
        if(arr.size()==0) continue;
        if(arr.size()>1) 
            arr = AddEle(arr, ans);
        for(int i=0; i<arr.size(); i++){
            board[i][c] = arr[i];
        }
        arr.clear();
    }
}

void MoveDown(vector<vector<int>>& board, int& ans){
    vector<int> arr;
    int n = board.size();
    for(int c=0; c<n; c++){
        for(int r=n-1; r>=0; r--){
            if(board[r][c]==0) continue;
            arr.push_back(board[r][c]);
            board[r][c]=0;
        }
        if(arr.size()==0) continue;
        if(arr.size()>1) 
            arr = AddEle(arr, ans);
        for(int i=0; i<arr.size(); i++){
            board[n-1-i][c] = arr[i];
        }
        arr.clear();
    }
}

void MoveLeft(vector<vector<int>>& board, int& ans){
    vector<int> arr;
    int n = board.size();
    for(int r=0; r<n; r++){
        for(int c=0; c<n; c++){
            if(board[r][c]==0) continue;
            arr.push_back(board[r][c]);
            board[r][c]=0;
        }
        if(arr.size()==0) continue;
        if(arr.size()>1) 
            arr = AddEle(arr, ans);
        for(int i=0; i<arr.size(); i++){
            board[r][i] = arr[i];
        }
        arr.clear();
    }
}

void MoveRight(vector<vector<int>>& board, int& ans){
    vector<int> arr;
    int n = board.size();
    for(int r=0; r<n; r++){
        for(int c=n-1; c>=0; c--){
            if(board[r][c]==0) continue;
            arr.push_back(board[r][c]);
            board[r][c]=0;
        }
        if(arr.size()==0) continue;
        if(arr.size()>1) 
            arr = AddEle(arr, ans);
        for(int i=0; i<arr.size(); i++){
            board[r][n-1-i] = arr[i];
        }
        arr.clear();
    }
}


void MoveInterface(vector<vector<int>>& board, int dir, int& ans){
    // dir 0,1,2,3 -> 상,하,좌,우
    if(dir==0) MoveUp(board, ans);
    else if(dir==1) MoveDown(board, ans);
    else if(dir==2) MoveLeft(board, ans);
    else if(dir==3) MoveRight(board, ans);
}

void Dfs(vector<vector<int>>& board, int& ans, int cnt){
    if(cnt==5) return;

    vector<vector<int>> cboard;
    for(int dir=0; dir<4; dir++){
        cboard = board;
        MoveInterface(board, dir, ans);
        Dfs(board, ans, cnt+1);
        board = cboard;
    }
}

int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int N;
    cin >> N;
    int ans = 0;
    vector<vector<int>> board(N, vector<int>(N,0));
    for(int r=0; r<N; r++){
        for(int c=0; c<N; c++){
            cin >> board[r][c];
            if(ans<board[r][c]) 
                ans = board[r][c]; // 합쳐질 수 있는 경우가 없을 수도 있으므로
        }
    }
    Dfs(board, ans, 0);
    cout << ans << endl;

    return 0;
}