Category: 시뮬레이션

2021
0
ProgrammingBeakjoon

백준 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;}

0
ProgrammingBeakjoon

백준 - 14499 주사위 굴리기

https://www.acmicpc.net/problem/14499 체점 현황 문제 해설문제를 입력받는 곳에서 함정이 있다. 평소에 세로를 y, 가로를 x로 놓고 문제를 해결하는 사람들에게는 틀리기 너무 좋은 문제주사위의 현재 위치를 계속 추적하면서 주사위 상태도 계속해서 관리해야 한다. 위치를 쉽게 관리하기 위해서 전역변수를 통해 전역적으로 관리했다. #include <iostream>#include <vector>using namespace std;int n, m, x, y, k;int map[22][22];int cube[4][3];vector<int> command;void moveUp() { if (x - 1 >= 0) { x -= 1; int temp01, temp11, temp21, temp31; temp01 = cube[0][1]; temp11 = cube[1][1]; temp21 = cube[2][1]; temp31 = cube[3][1]; cube[0][1] = temp11; cube[1][1] = temp21; cube[2][1] = temp31; cube[3][1] = temp01; int next = map[x][y]; if (next == 0) { map[x][y] = cube[3][1]; } else { cube[3][1] = map[x][y]; map[x][y] = 0; } cout << cube[1][1] << '\n'; } else { return; }}void moveDown() { if (x + 1 < n) { x += 1; int temp01, temp11, temp21, temp31; temp01 = cube[0][1]; temp11 = cube[1][1]; temp21 = cube[2][1]; temp31 = cube[3][1]; cube[1][1] = temp01; cube[2][1] = temp11; cube[3][1] = temp21; cube[0][1] = temp31; int next = map[x][y]; if (next == 0) { map[x][y] = cube[3][1]; } else { cube[3][1] = map[x][y]; map[x][y] = 0; } cout << cube[1][1] << '\n'; } else { return; }}void moveRight() { if (y + 1 < m) { y += 1; int temp11, temp12, temp31, temp10; temp11 = cube[1][1]; temp12 = cube[1][2]; temp31 = cube[3][1]; temp10 = cube[1][0]; cube[1][1] = temp10; cube[1][2] = temp11; cube[3][1] = temp12; cube[1][0] = temp31; int next = map[x][y]; if (next == 0) { map[x][y] = cube[3][1]; } else { cube[3][1] = map[x][y]; map[x][y] = 0; } cout << cube[1][1] << '\n'; } else { return; }}void moveLeft() { if (y - 1 >= 0) { y -= 1; int temp11, temp12, temp31, temp10; temp11 = cube[1][1]; temp12 = cube[1][2]; temp31 = cube[3][1]; temp10 = cube[1][0]; cube[1][0] = temp11; cube[1][1] = temp12; cube[1][2] = temp31; cube[3][1] = temp10; int next = map[x][y]; if (next == 0) { map[x][y] = cube[3][1]; } else { cube[3][1] = map[x][y]; map[x][y] = 0; } cout << cube[1][1] << '\n'; } else { return; }}void moveCube() { int commandNum = command.size(); for (int i = 0; i < commandNum; i++) { int cntCommand = command[i]; if (cntCommand == 1) { moveRight(); } if (cntCommand == 2) { moveLeft(); } if (cntCommand == 3) { moveUp(); } if (cntCommand == 4) { moveDown(); } }}int main(void) { cin >> n >> m >> x >> y >> k; for (int i = 0; i < n; i++) { { for (int j = 0; j < m; j++) { cin >> map[i][j]; } } } map[x][y] = 0; for (int i = 0; i < k; i++) { int temp = 0; cin >> temp; command.push_back(temp); } moveCube(); return 0;}