https://www.acmicpc.net/problem/12100
이번 시간에는 백준 12100번 구현 및 dfs에 대해서 풀어보겠습니다.
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
#include <iostream>
#include <vector>
#include <cmath>
// ToDo
// 이 게임은 중간에 공백이 들어갈 수 있음. 나는 무조건 연속된 수가 나온다고 생각하고 짰다.
//
enum Direction {
LEFT,
UP,
RIGHT,
DOWN
};
template <class container>
class Board {
public:
const int board_size;
const container board;
int max_value = 0;
Board(int board_size, container board_value) :board_size(board_size), board(board_value) {
for (auto& board_row : board_value) {
for (auto& value : board_row) {
if (this->max_value < value)
this->max_value = value;
}
}
}
container move_left(container board) {
for (int row = 0; row < board_size; ++row) {
for (int column = 0; column < board_size; ++column) {
bool is_empty = (board[row][column] == 0); // 비었을 시
if (is_empty) {
int column_current = column;
while (column_current < board_size) {
if (board[row][column_current] != 0) {
int tmp_container = board[row][column];
board[row][column] = board[row][column_current];
board[row][column_current] = tmp_container;
break;
}
column_current++;
}
}
}
}
for (int row = 0; row < board_size; ++row) {
for (int column = 0; column < board_size - 1; ++column) {
bool is_same = (board[row][column] == board[row][column + 1] && board[row][column] != 0); // 좌측으로 이동하였을 때, 인접한 두블럭의 값이 같으면 합쳐짐.
if (is_same) {
board[row][column] *= 2;
board[row][column + 1] = 0;
}
}
}
for (int row = 0; row < board_size; ++row) {
for (int column = 0; column < board_size; ++column) {
bool is_empty = (board[row][column] == 0); // 비었을 시
if (is_empty) {
int column_current = column;
while (column_current < board_size) {
if (board[row][column_current] != 0) {
int tmp_container = board[row][column];
board[row][column] = board[row][column_current];
board[row][column_current] = tmp_container;
break;
}
column_current++;
}
}
}
}
return board;
}
container move_up(container board) {
for (int column = 0; column < board_size; ++column) {
for (int row = 0; row < board_size; ++row) {
bool is_empty = (board[row][column] == 0); // 비었을 시
if (is_empty) {
int row_current = row;
while (row_current < board_size) {
if (board[row_current][column] != 0) {
int tmp_container = board[row][column];
board[row][column] = board[row_current][column];
board[row_current][column] = tmp_container;
break;
}
row_current++;
}
}
}
}
for (int column = 0; column < board_size; ++column) {
for (int row = 0; row < board_size - 1; ++row) {
bool is_same = (board[row][column] == board[row + 1][column] && board[row][column] != 0); // 위측으로 이동하였을 때, 인접한 두블럭의 값이 같으면 합쳐짐.
if (is_same) {
board[row][column] *= 2;
board[row + 1][column] = 0;
}
}
}
for (int column = 0; column < board_size; ++column) {
for (int row = 0; row < board_size; ++row) {
bool is_empty = (board[row][column] == 0); // 비었을 시
if (is_empty) {
int row_current = row;
while (row_current < board_size) {
if (board[row_current][column] != 0) {
int tmp_container = board[row][column];
board[row][column] = board[row_current][column];
board[row_current][column] = tmp_container;
break;
}
row_current++;
}
}
}
}
return board;
}
container move_right(container board) {
for (int row = 0; row < board_size; ++row) {
for (int column = board_size - 1; column >= 0; --column) {
bool is_empty = (board[row][column] == 0); // 비었을 시
if (is_empty) {
int column_current = column;
while (column_current >= 0) {
if (board[row][column_current] != 0) {
int tmp_container = board[row][column];
board[row][column] = board[row][column_current];
board[row][column_current] = tmp_container;
break;
}
column_current--;
}
}
}
}
for (int row = 0; row < board_size; ++row) {
for (int column = board_size - 1; column > 0; --column) {
bool is_same = (board[row][column] == board[row][column - 1] && board[row][column] != 0); // 우측으로 이동하였을 때, 인접한 두블럭의 값이 같으면 합쳐짐.
if (is_same) {
board[row][column] *= 2;
board[row][column - 1] = 0;
}
}
}
for (int row = 0; row < board_size; ++row) {
for (int column = board_size - 1; column >= 0; --column) {
bool is_empty = (board[row][column] == 0); // 비었을 시
if (is_empty) {
int column_current = column;
while (column_current >= 0) {
if (board[row][column_current] != 0) {
int tmp_container = board[row][column];
board[row][column] = board[row][column_current];
board[row][column_current] = tmp_container;
break;
}
column_current--;
}
}
}
}
return board;
}
container move_down(container board) {
for (int column = 0; column < board_size; ++column) {
for (int row = board_size - 1; row >= 0; --row) {
bool is_empty = (board[row][column] == 0); // 비었을 시
if (is_empty) {
int row_current = row;
while (row_current >= 0) {
if (board[row_current][column] != 0) {
int tmp_container = board[row][column];
board[row][column] = board[row_current][column];
board[row_current][column] = tmp_container;
break;
}
row_current--;
}
}
}
}
for (int column = 0; column < board_size; ++column) {
for (int row = board_size - 1; row > 0; --row) {
bool is_same = (board[row][column] == board[row - 1][column] && board[row][column] != 0); // 아래측으로 이동하였을 때, 인접한 두블럭의 값이 같으면 합쳐짐.
if (is_same) {
board[row][column] *= 2;
board[row - 1][column] = 0;
}
}
}
for (int column = 0; column < board_size; ++column) {
for (int row = board_size - 1; row >= 0; --row) {
bool is_empty = (board[row][column] == 0); // 비었을 시
if (is_empty) {
int row_current = row;
while (row_current >= 0) {
if (board[row_current][column] != 0) {
int tmp_container = board[row][column];
board[row][column] = board[row_current][column];
board[row_current][column] = tmp_container;
break;
}
row_current--;
}
}
}
}
return board;
}
container board_move(container board, Direction direction) {
container board_result;
if (direction == LEFT)
board_result = move_left(board);
else if (direction == UP)
board_result = move_up(board);
else if (direction == RIGHT)
board_result = move_right(board);
else if (direction == DOWN)
board_result = move_down(board);
return board_result;
}
int get_board_max_value(const container& board) const {
int max_val = 0;
for (auto& board_row : board) {
for (auto& value : board_row) {
if (max_val < value)
max_val = value;
}
}
return max_val;
}
void dfs(container board, int count) {
if (count == 5) {
int max_val = get_board_max_value(board);
if (this->max_value < max_val)
this->max_value = max_val;
return;
}
dfs(this->board_move(board, LEFT), count + 1);
dfs(this->board_move(board, UP), count + 1);
dfs(this->board_move(board, RIGHT), count + 1);
dfs(this->board_move(board, DOWN), count + 1);
}
};
void set_board_size(int& board_size);
void set_board(int& board_size, std::vector<std::vector<int>>& board_value);
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int board_size; std::vector<std::vector<int>> board_value;
set_board_size(board_size);
set_board(board_size, board_value);
Board<std::vector<std::vector<int>>>* board = new Board<std::vector<std::vector<int>>>(board_size, board_value);
board->dfs(board->board, 0);
std::cout << board->max_value;
return 0;
}
void set_board_size(int& board_size) {
std::cin >> board_size;
if (board_size < 1)
board_size = 1;
else if (board_size > 20)
board_size = 20;
}
void set_board(int& board_size, std::vector<std::vector<int>>& board_value) {
board_value.resize(board_size, std::vector<int>(board_size, 0));
for (int i = 0; i < board_size; ++i) {
for (int j = 0; j < board_size; ++j) {
std::cin >> board_value[i][j];
}
}
}
dfs부분에서 재귀로 짜고 있다가 for문에 집어넣어서 마치 stack으로 구현한 것 처럼 이상하게 짜서 시간초과가 났었다. dfs는 재귀아니면 stack으로 구현할 수 있는데 분명히 구분해야한다!
'백준' 카테고리의 다른 글
| 11659번 (Silver 3) (0) | 2025.01.09 |
|---|---|
| 백준 3190번(Gold 4) (1) | 2023.11.22 |
| 백준 13460번(Gold 1) (0) | 2023.10.15 |
| 백준 15686번(Gold 4) (1) | 2023.10.13 |
| 백준 2015번(Gold 4) (0) | 2023.10.05 |