문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

입출력 예

풀이

모든 경우를 다 해본다.
각 라인을 이동시킬 때
1. 0이 아닌 원소를 큐에 offer
2. 다음 원소와 1의 원소가 같다면 다음 원소까지 offer 후 더한 값을 배열에 넣음

코드

import java.io.*;
import java.util.*;
public class Main_B12100 {
	static int n,answer=0;
	//5번 이동을 위한 dfs
	static void dfs(int depth,int[][]arr) {
		if(depth==5) {
			answer=Math.max(answer, getMax(arr));
			return;
		}
		for(int i=0;i<4;i++) {			
			dfs(depth+1,move(i,arr));
		}
	}
	//각 배열의 최댓값 찾는 메서드
	static int getMax(int[][]arr) {
		int temp=0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(arr[i][j]>temp)temp=arr[i][j];
			}
		}
		return temp;
	}
	//한 라인씩 이동
	static void lineMove(int[][]arr,Queue<Integer> q,int i,int d){
		int[]temp=new int[n];
		int num=0,index=0;
		while(!q.isEmpty()) {
			if(num==0)num=q.poll();
			if(!q.isEmpty()&&num==q.peek()) {
				q.poll();
				temp[index++]=num*2;
			}
			else temp[index++]=num;
			num=0;
		}
        //상
		if(d==0)for(int k=0;k<n;k++)arr[k][i]=temp[k];
		//하
        else if(d==1)for(int k=0;k<n;k++)arr[n-k-1][i]=temp[k];
        //좌
		else if(d==2)for(int k=0;k<n;k++)arr[i][k]=temp[k];
		//우
        else for(int k=0;k<n;k++)arr[i][n-k-1]=temp[k];
	}
	//각 방향으로 배열 이동
	static int[][] move(int d,int[][]arr) {
		Queue<Integer> q = new LinkedList<>();
		int[][]map=new int[n][n];
		if(d==0) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(arr[j][i]!=0)q.offer(arr[j][i]);
				}
				lineMove(map,q,i,d);
			}
		}
		else if(d==1) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(arr[n-j-1][i]!=0)q.offer(arr[n-j-1][i]);
				}
				lineMove(map,q,i,d);
			}
		}
		else if(d==2) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(arr[i][j]!=0)q.offer(arr[i][j]);
				}
				lineMove(map,q,i,d);
			}
		}
		else {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(arr[i][n-j-1]!=0)q.offer(arr[i][n-j-1]);
				}
				lineMove(map,q,i,d);
			}
		}
		return map;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n=Integer.parseInt(br.readLine());
		
		int[][]arr=new int[n][n];
		for(int i=0;i<n;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				arr[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		dfs(0, arr);
		System.out.println(answer);
	}

}