Tag: 시뮬레이션

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

백준 3190 - 뱀

https://www.acmicpc.net/problem/3190 체점 현황 전체 소스 코드#include <bits/stdc++.h>using namespace std;int board[110][110];int board_size;int num_of_apple;int num_of_command;map<int, char> command;// 동, 남, 서, 북int dx[4] = {1, 0, -1, 0};int dy[4] = {0, 1, 0, -1};int direction[4] = {0, 1, 2, 3};struct snake { int y; int x; int dir;};int main(void) { cin >> board_size >> num_of_apple; for (int i = 0; i < num_of_apple; i++) { int y, x; cin >> y >> x; board[y][x] = 1; } cin >> num_of_command; for (int i = 0; i < num_of_command; i++) { int time; char dir; cin >> time >> dir; command[time] = dir; } queue<pair<int, int>> snake_tail; int snake_head_y = 1; int snake_haed_x = 1; int snake_dir = 0; snake_tail.push({1, 1}); board[1][1] = 2; int time = 0; while (true) { time++; snake_head_y += dy[snake_dir]; snake_haed_x += dx[snake_dir]; snake_tail.push({snake_head_y, snake_haed_x}); if (board[snake_head_y][snake_haed_x] == 2) { cout << time << '\n'; return 0; } if (0 >= snake_head_y || snake_head_y > board_size || 0 >= snake_haed_x || snake_haed_x > board_size) { cout << time << '\n'; return 0; } if (board[snake_head_y][snake_haed_x] == 1) { board[snake_head_y][snake_haed_x] = 2; } else { board[snake_head_y][snake_haed_x] = 2; board[snake_tail.front().first][snake_tail.front().second] = 0; snake_tail.pop(); } if (command.find(time) != command.end()) { char com = command[time]; command.erase(time); if (com == 'L') { snake_dir = (snake_dir + 3) % 4; } else { snake_dir = (snake_dir + 1) % 4; } } } return 0;}