백준 푸는거 진짜 오랜만인데 골드2부터 다시 풀어보려고 한다.
처음부터 다시 하려고 계정도 새로 팠으니 문제 풀다가 중간중간 solved.ac 도 캡쳐해서 올리도록 하겠다.
2048(easy) 문제는 정말 easy한데, ps 푸는게 너무 오랜만이라 생각보다 시간이 좀 걸렸다.
상하좌우로 이동을 시키는 함수를 짜고, dfs로 5번 이동을 모든 경우에 대해 해보면서 최대값을 찾으면 된다.
상하좌우로 이동 시키는 함수를 잘못 짜서 고생했는데 처음에는 만약 위로 이동한다고 하면,
위에서부터 하나씩 위로 이동시키면서 같으면 2배, 비었으면 이동 이런 식으로 짰는데 이렇게 하면 위에서 한번 합쳐진 블록이 또 합쳐질 수 있어서 안된다.
그래서 그냥 합치는거 빼고 빈칸인 경우에 이동시키는 걸로 위로 블록들을 올린 다음, 인접한 두 블록이 같으면 합치고, 또 위로 블록들을 올렸다.
void up()
{
for(int i=1;i<=N;i++)
{
for(int j=2;j<=N;j++)
{
int k=j-1;
while(k>=1)
{
if(state[k][i]!=0) break;
k--;
}
if(k+1!=j){
state[k+1][i]=state[j][i];
state[j][i]=0;
}
}
}
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
if(state[j][i]==state[j+1][i])
{
state[j][i]*=2;
state[j+1][i]=0;
}
}
}
for(int i=1;i<=N;i++)
{
for(int j=2;j<=N;j++)
{
int k=j-1;
while(k>=1)
{
if(state[k][i]!=0) break;
k--;
}
if(k+1!=j){
state[k+1][i]=state[j][i];
state[j][i]=0;
}
}
}
}이렇게 하고, dfs는 그냥 하면 된다.
근데 상태를 저장하기 위해 tmp 배열 따로 만드는 것만 생각해주면 된다.
이번 문제는 딱히 설명할게 없어서 빠르게 넘어가겠다.
오랜만에 맞왜틀 고치느라 좀 힘들었다.
아래는 전체 코드이다.
#include<stdio.h>
int N;
int ans=0;
int state[100][100];
void up()
{
for(int i=1;i<=N;i++)
{
for(int j=2;j<=N;j++)
{
int k=j-1;
while(k>=1)
{
if(state[k][i]!=0) break;
k--;
}
if(k+1!=j){
state[k+1][i]=state[j][i];
state[j][i]=0;
}
}
}
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
if(state[j][i]==state[j+1][i])
{
state[j][i]*=2;
state[j+1][i]=0;
}
}
}
for(int i=1;i<=N;i++)
{
for(int j=2;j<=N;j++)
{
int k=j-1;
while(k>=1)
{
if(state[k][i]!=0) break;
k--;
}
if(k+1!=j){
state[k+1][i]=state[j][i];
state[j][i]=0;
}
}
}
}
void down()
{
for(int i=1;i<=N;i++)
{
for(int j=N-1;j>=1;j--)
{
int k=j+1;
while(k<=N)
{
if(state[k][i]!=0) break;
k++;
}
if(k-1!=j){
state[k-1][i]=state[j][i];
state[j][i]=0;
}
}
}
for(int i=1;i<=N;i++)
{
for(int j=N;j>=1;j--)
{
if(state[j][i]==state[j-1][i])
{
state[j][i]*=2;
state[j-1][i]=0;
}
}
}
for(int i=1;i<=N;i++)
{
for(int j=N-1;j>=1;j--)
{
int k=j+1;
while(k<=N)
{
if(state[k][i]!=0) break;
k++;
}
if(k-1!=j){
state[k-1][i]=state[j][i];
state[j][i]=0;
}
}
}
}
void right()
{
for(int i=1;i<=N;i++)
{
for(int j=N-1;j>=1;j--)
{
int k=j+1;
while(k<=N)
{
if(state[i][k]!=0) break;
k++;
}
if(k-1!=j){
state[i][k-1]=state[i][j];
state[i][j]=0;
}
}
}
for(int i=1;i<=N;i++)
{
for(int j=N;j>=1;j--)
{
if(state[i][j]==state[i][j-1])
{
state[i][j]*=2;
state[i][j-1]=0;
}
}
}
for(int i=1;i<=N;i++)
{
for(int j=N-1;j>=1;j--)
{
int k=j+1;
while(k<=N)
{
if(state[i][k]!=0) break;
k++;
}
if(k-1!=j){
state[i][k-1]=state[i][j];
state[i][j]=0;
}
}
}
}
void left()
{
for(int i=1;i<=N;i++)
{
for(int j=2;j<=N;j++)
{
int k=j-1;
while(k>=1)
{
if(state[i][k]!=0) break;
k--;
}
if(k+1!=j){
state[i][k+1]=state[i][j];
state[i][j]=0;
}
}
}
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
if(state[i][j]==state[i][j+1])
{
state[i][j]*=2;
state[i][j+1]=0;
}
}
}
for(int i=1;i<=N;i++)
{
for(int j=2;j<=N;j++)
{
int k=j-1;
while(k>=1)
{
if(state[i][k]!=0) break;
k--;
}
if(k+1!=j){
state[i][k+1]=state[i][j];
state[i][j]=0;
}
}
}
}
void mov(int x)
{
if(x==1) up();
if(x==2) down();
if(x==3) right();
if(x==4) left();
}
int maxvalue()
{
int x=0;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
if(x<state[i][j]) x=state[i][j];
}
}
return x;
}
void test(int step)
{
if(step>5)
{
if(ans<maxvalue()) ans=maxvalue();
return;
}
int tmp[100][100];
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
tmp[i][j]=state[i][j];
}
}
for(int x=1;x<=4;x++)
{
mov(x);
test(step+1);
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
state[i][j]=tmp[i][j];
}
}
}
}
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
scanf("%d",&state[i][j]);
}
}
test(1);
printf("%d",ans);
}
