백준 12100 - 2048
https://www.acmicpc.net/problem/12100 백준 12100 - 2048문제 풀이보드를 상하좌우로 움직이면서 블록이 최대값이 나올 수 있는 경우를 찾는 문제이다. 한 보드를 상하좌우로 움직이고 원래데로 되돌린 후 다시 시도하기 위해 백트레킹 기법이 필요하다. 블록을 상하좌우중 한 방향으로 움직인다. 5번 움직이면 블록을 스캔해 최대값을 찾는다. 이전 단계로 되돌린 후 다른방향으로 움직이면서 최대값을 찾아본다. 문제 예외 처리 한번 합처진 블록은 연속적으로 합처질 수 없다. 합처지는 순서는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 소스 코드#include <bits/stdc++.h>using namespace std;int maxValue = 0;int board[22][22];int boardSize = 0;void initBoard(int size) { for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { cin >> board[i][j]; } }}void moveTop() { int check[22][22]; for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { check[col][row] = false; } } for (int row = 0; row < boardSize; row++) { for (int col = 0; col < boardSize; col++) { int cntRow = row; int cntCol = col; if (board[cntRow][cntCol] == 0) { continue; } while (cntRow - 1 >= 0 && (board[cntRow - 1][cntCol] == board[cntRow][cntCol] || board[cntRow - 1][cntCol] == 0)) { if (board[cntRow - 1][cntCol] == board[cntRow][cntCol]) { if (check[cntRow - 1][cntCol] == false && check[cntRow][cntCol] == false) { board[cntRow - 1][cntCol] += board[cntRow][cntCol]; check[cntRow - 1][cntCol] = true; board[cntRow][cntCol] = 0; } else { break; } } else { swap(board[cntRow - 1][cntCol], board[cntRow][cntCol]); } cntRow--; } } }}void moveButton() { int check[22][22]; for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { check[col][row] = false; } } for (int row = boardSize - 1; row >= 0; row--) { for (int col = 0; col < boardSize; col++) { int cntCol = col; int cntRow = row; if (board[cntRow][cntCol] == 0) { continue; } while (cntRow + 1 < boardSize && (board[cntRow + 1][cntCol] == board[cntRow][cntCol] || board[cntRow + 1][cntCol] == 0)) { if (board[cntRow + 1][cntCol] == board[cntRow][cntCol]) { if (check[cntRow + 1][cntCol] == false && check[cntRow][cntCol] == false) { board[cntRow + 1][cntCol] += board[cntRow][cntCol]; check[cntRow + 1][cntCol] = true; board[cntRow][cntCol] = 0; } else { break; } } else { swap(board[cntRow + 1][cntCol], board[cntRow][cntCol]); } cntRow++; } } }}void moveLeft() { int check[22][22]; for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { check[col][row] = false; } } for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { int cntCol = col; int cntRow = row; if (board[cntRow][cntCol] == 0) { continue; } while (cntCol - 1 >= 0 && (board[cntRow][cntCol - 1] == board[cntRow][cntCol] || board[cntRow][cntCol - 1] == 0)) { if (board[cntRow][cntCol - 1] == board[cntRow][cntCol]) { if (check[cntRow][cntCol - 1] == false && check[cntRow][cntCol] == false) { board[cntRow][cntCol - 1] += board[cntRow][cntCol]; check[cntRow][cntCol - 1] = true; board[cntRow][cntCol] = 0; } else { break; } } else { swap(board[cntRow][cntCol - 1], board[cntRow][cntCol]); } cntCol--; } } }}void moveRight() { int check[22][22]; for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { check[col][row] = false; } } for (int col = boardSize - 1; col >= 0; col--) { for (int row = 0; row < boardSize; row++) { int cntRow = row; int cntCol = col; if (board[cntRow][cntCol] == 0) { continue; } while (cntCol + 1 < boardSize && (board[cntRow][cntCol + 1] == board[cntRow][cntCol] || board[cntRow][cntCol + 1] == 0)) { if (board[cntRow][cntCol + 1] == board[cntRow][cntCol]) { if (check[cntRow][cntCol + 1] == false && check[cntRow][cntCol] == false) { board[cntRow][cntCol + 1] += board[cntRow][cntCol]; check[cntRow][cntCol + 1] = true; board[cntRow][cntCol] = 0; } else { break; } } else { swap(board[cntRow][cntCol], board[cntRow][cntCol + 1]); } cntCol++; } } }}void returnBoard(int (*board)[22], int (*copy)[22]) { for (int i = 0; i < boardSize; i++) { for (int j = 0; j < boardSize; j++) { board[i][j] = copy[i][j]; } }}void moveBoard(int depth) { int copyBoard[22][22]; for (int i = 0; i < boardSize; i++) { for (int j = 0; j < boardSize; j++) { copyBoard[i][j] = board[i][j]; } } if (depth == 5) { for (int i = 0; i < boardSize; i++) { for (int j = 0; j < boardSize; j++) { if (board[i][j] > maxValue) { maxValue = board[i][j]; } } } return; } moveTop(); moveBoard(depth + 1); returnBoard(board, copyBoard); moveButton(); moveBoard(depth + 1); returnBoard(board, copyBoard); moveLeft(); moveBoard(depth + 1); returnBoard(board, copyBoard); moveRight(); moveBoard(depth + 1); returnBoard(board, copyBoard);}int main(void) { cin >> boardSize; initBoard(boardSize); moveBoard(0); cout << maxValue << '\n'; return 0;}