Study hard
(c++)백준 12100번: 2048 (Easy) 본문
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net






[풀이]
dfs 중복순열을 구하는 방법을 이용하여 5번 이동시키는 모든 경우에 대해 얻을 수 있는 가장 큰 블록을 구하였다.
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int Board[20][20];
int c_Board[20][20];
int Order[5];
const int dx[] = { -1,1,0,0 };//위,아래
const int dy[] = { 0,0,-1,1 };//왼,오
int Max = -1;
void copyBoard() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
c_Board[i][j] = Board[i][j];
}
}
}
void MoveUp() {
//1행부터
for (int x = 1; x < N; x++) {
for (int y = 0; y < N; y++) {
if (c_Board[x][y] == 0)
continue;
//바로 윗칸이 빈칸이면
if (c_Board[x - 1][y] == 0) {
int nx = x + dx[0];
//빈칸 아닐때까지
while (c_Board[nx][y] == 0) {
nx += dx[0];
if (nx < 0)
break;
}
nx -= dx[0];
c_Board[nx][y] = c_Board[x][y];
c_Board[x][y] = 0;
}
}
}
}
void MoveDown() {
//N-2행부터
for (int x = N - 2; x >= 0; x--) {
for (int y = 0; y < N; y++) {
if (c_Board[x][y] == 0)
continue;
//바로 아래칸이 빈칸이면
if (c_Board[x + 1][y] == 0) {
int nx = x + dx[1];
//빈칸 아닐 때까지
while (c_Board[nx][y] == 0) {
nx += dx[1];
if (nx >= N)
break;
}
nx -= dx[1];
c_Board[nx][y] = c_Board[x][y];
c_Board[x][y] = 0;
}
}
}
}
void MoveLeft() {
//1열부터
for (int y = 1; y < N; y++) {
for (int x = 0; x < N; x++) {
if (c_Board[x][y] == 0)
continue;
//바로 왼쪽칸이 빈칸이면
if (c_Board[x][y - 1] == 0) {
int ny = y + dy[2];
//빈칸 아닐 때까지
while (c_Board[x][ny] == 0) {
ny += dy[2];
if (ny < 0)
break;
}
ny -= dy[2];
c_Board[x][ny] = c_Board[x][y];
c_Board[x][y] = 0;
}
}
}
}
void MoveRight() {
//N-2열부터
for (int y = N - 2; y >= 0; y--) {
for (int x = 0; x < N; x++) {
if (c_Board[x][y] == 0)
continue;
//바로 오른쪽칸이 빈칸이면
if (c_Board[x][y + 1] == 0) {
int ny = y + dy[3];
//빈칸 아닐 때까지
while (c_Board[x][ny] == 0) {
ny += dy[3];
if (ny >= N)
break;
}
ny -= dy[3];
c_Board[x][ny] = c_Board[x][y];
c_Board[x][y] = 0;
}
}
}
}
void MergeUp() {
//아래칸과 같은 블록 있으면 합치기
for (int x = 0; x < N - 1; x++) {
for (int y = 0; y < N; y++) {
if (c_Board[x][y] == 0)
continue;
if (c_Board[x][y] == c_Board[x + 1][y]) {
c_Board[x][y] = 2 * c_Board[x][y];
c_Board[x + 1][y] = 0;
Max = max(Max, c_Board[x][y]);
}
}
}
}
void MergeDown() {
//윗칸과 같은 블록 있으면 합치기
for (int x = N - 1; x > 0; x--) {
for (int y = 0; y < N; y++) {
if (c_Board[x][y] == 0)
continue;
if (c_Board[x][y] == c_Board[x - 1][y]) {
c_Board[x][y] = 2 * c_Board[x][y];
c_Board[x - 1][y] = 0;
Max = max(Max, c_Board[x][y]);
}
}
}
}
void MergeLeft() {
//0열부터
for (int y = 0; y < N - 1; y++) {
for (int x = 0; x < N; x++) {
if (c_Board[x][y] == 0)
continue;
//오른쪽 칸과 블록이 같으면
if (c_Board[x][y] == c_Board[x][y + 1]) {
c_Board[x][y] = 2 * c_Board[x][y];
c_Board[x][y + 1] = 0;
Max = max(Max, c_Board[x][y]);
}
}
}
}
void MergeRight() {
//N-1열부터
for (int y = N - 1; y > 0; y--) {
for (int x = 0; x < N; x++) {
if(c_Board[x][y] == 0)
continue;
//왼쪽칸과 블록이 같으면
if (c_Board[x][y] == c_Board[x][y - 1]) {
c_Board[x][y] = 2 * c_Board[x][y];
c_Board[x][y - 1] = 0;
Max = max(Max, c_Board[x][y]);
}
}
}
}
void Move() {
copyBoard();
for (int i = 0; i < 5; i++) {
int d = Order[i];
//위로
if (d == 0) {
MoveUp();
MergeUp();
MoveUp();
}
//아래로
else if (d == 1) {
MoveDown();
MergeDown();
MoveDown();
}
//왼쪽으로
else if (d == 2) {
MoveLeft();
MergeLeft();
MoveLeft();
}
//오른쪽으로
else if (d == 3) {
MoveRight();
MergeRight();
MoveRight();
}
}
}
//중복 순열 구하기
void getOrder(int cnt) {
if (cnt == 5) {
Move();
return;
}
for (int i = 0; i < 4; i++) {
Order[cnt] = i;
getOrder(cnt + 1);
}
}
void solution() {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> Board[i][j];
Max = max(Max, Board[i][j]);
}
}
getOrder(0);
/*
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << Board[i][j] << ' ';
}
cout << '\n';
}*/
cout << Max << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solution();
return 0;
}
'백준 > bfs, dfs' 카테고리의 다른 글
(c++)백준 14889번: 스타트와 링크 (0) | 2020.10.17 |
---|---|
(c++)백준 15684번: 사다리 조작 (0) | 2020.10.16 |
(c++)백준 13460번: 구슬 탈출 2 (0) | 2020.10.16 |
(c++)백준 16234번: 인구 이동 (0) | 2020.10.15 |
(c++)백준 15683번: 감시 (0) | 2020.10.15 |