https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
문제해석
그림생략
평범한 2048게임과 같은 규칙이다. 단 새로은 블록이 추가되지 않는다는 차이 점이 있다.
최대 5번 움직일수있고 상하좌우 4방향이므로 총 4^5 = 1024 가지의 경우가 존재한다.
그래서 제한시간에비해 경우가 적으므로 전부 다 해보는 것으로 하기로 결정했다.
상하좌우의 경우에 따라 move함수를 구현했는데 이게 보니까 200줄이 넘는다.
사실 반복문의 시작위치랑 인덱스정도만 다르고 템플릿은 같기때문에 그것만 조심해서 복붙만한다면 별거없다.
문제는 오타만 내지 않으면 되는데 오타내서 3번이나 틀려먹었다.
일반 배열이 아니라 pair 배열을 선언했는데 first부분은 2 4 8 16 32 ... 의 숫자정보가 들어가는 곳으로
second 부분은 이 블럭이 같은 숫자의 블럭과 합쳐 질 수 있는가의 정보가 들어가는 곳으로 활용하였다.
second=0 -> 합칠 수 있음 second=1 -> 합칠 수 없음
또한 move한다는거는 한쪽으로 밀어 넣는것이니 큐나 스택을 활용하여 밀어 넣을수있는데 난 스택을 사용해서 밀어넣었다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
void dfs(int depth);
void move(int d);
stack <int> st[20];
vector <int> v;
int direction[4]={0,1,2,3}; //오 왼 위 아
pair<int,int> p[20][20];
pair<int,int> original[20][20];
int n;
int ans=0;
int main(){
cout.tie(NULL);
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin>>n;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
cin>>original[i][j].first;
original[i][j].second=0;
}
}
dfs(0);
cout<<ans;
}
void dfs(int depth){
if(depth==5)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
p[i][j]=original[i][j];
}
}
for(int i=0; i<v.size(); i++)
{
move(v[i]);
}
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
ans=max(ans,p[i][j].first);
}
}
return;
}
for(int i=0; i<4; i++)
{
v.push_back(direction[i]);
dfs(depth+1);
v.pop_back();
}
}
void move(int d){
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
p[i][j].second=0;
}
}
int index;
int x;
if(d==0)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(p[i][j].first!=0)
{
st[i].push(p[i][j].first);
p[i][j].first=0;
}
}
}
for(int i=0; i<n; i++)
{
index=n-1;
while(!st[i].empty())
{
x=st[i].top();
st[i].pop();
if(index==n-1)
{
p[i][index].first=x;
index--;
}
else
{
if(p[i][index+1].first==x)
{
if(p[i][index+1].second==0)
{
p[i][index+1].first=x+x;
p[i][index+1].second=1;
}
else
{
p[i][index].first=x;
index--;
}
}
else
{
p[i][index].first=x;
index--;
}
}
}
}
}
else if(d==1)
{
for(int i=0; i<n; i++)
{
for(int j=n-1; j>=0; j--)
{
if(p[i][j].first!=0)
{
st[i].push(p[i][j].first);
p[i][j].first=0;
}
}
}
for(int i=0; i<n; i++)
{
index=0;
while(!st[i].empty())
{
x=st[i].top();
st[i].pop();
if(index==0)
{
p[i][index].first=x;
index++;
}
else
{
if(p[i][index-1].first==x)
{
if(p[i][index-1].second==0)
{
p[i][index-1].first=x+x;
p[i][index-1].second=1;
}
else
{
p[i][index].first=x;
index++;
}
}
else
{
p[i][index].first=x;
index++;
}
}
}
}
}
else if(d==2)
{
for(int i=0; i<n; i++)
{
for(int j=n-1; j>=0; j--)
{
if(p[j][i].first!=0)
{
st[i].push(p[j][i].first);
p[j][i].first=0;
}
}
}
for(int i=0; i<n; i++)
{
index=0;
while(!st[i].empty())
{
x=st[i].top();
st[i].pop();
if(index==0)
{
p[index][i].first=x;
index++;
}
else
{
if(p[index-1][i].first==x)
{
if(p[index-1][i].second==0)
{
p[index-1][i].first=x+x;
p[index-1][i].second=1;
}
else
{
p[index][i].first=x;
index++;
}
}
else
{
p[index][i].first=x;
index++;
}
}
}
}
}
else if(d==3)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(p[j][i].first!=0)
{
st[i].push(p[j][i].first);
p[j][i].first=0;
}
}
}
for(int i=0; i<n; i++)
{
index=n-1;
while(!st[i].empty())
{
x=st[i].top();
st[i].pop();
if(index==n-1)
{
p[index][i].first=x;
index--;
}
else
{
if(p[index+1][i].first==x)
{
if(p[index+1][i].second==0)
{
p[index+1][i].first=x+x;
p[index+1][i].second=1;
}
else
{
p[index][i].first=x;
index--;
}
}
else
{
p[index][i].first=x;
index--;
}
}
}
}
}
}
'백준문제풀이' 카테고리의 다른 글
| 백준 문제 16234번 인구이동 문제풀이 c++ (0) | 2022.04.03 |
|---|---|
| 백준 문제 2573번 빙산 문제풀이 c++ (0) | 2022.04.03 |
| 백준 문제 9328번 열쇠 문제풀이 c++ (0) | 2022.04.03 |
| 백준 문제 1504번 특정한 최단 경로 문제풀이 c++ (0) | 2022.04.03 |
| 백준 문제 13977번 이항 계수와 쿼리 문제풀이 c++ (0) | 2022.04.03 |