Baekjoon 12100 2048 (Easy) JAVA

12100번: 2048 (Easy)

문제

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

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

<그림 1>	<그림 2>	<그림 3>

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>	<그림 5>	<그림 6>	<그림 7>

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>	<그림 9>

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>	<그림 11>	<그림 12>	<그림 13>

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

<그림 14>	<그림 15>

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

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

출력

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

풀이

2048 게임을 구현하는 문제이다.

완전 탐색을 이용하여 5번 이동할 수 있는 모든 경우의 수를 출력하는 문제이다.

핵심 부분은 배열을 복사하는 것이다.

배열을 매개변수로 보내면 원본 배열이 수정되기에, 각 단계마다 배열을 복사하여 복사한 배열을 이용하여 연산을 수행하는 것이다.

나머지는 이동하는 방향인데, 수행 시간을 줄이기 위해서라면 동일한 방향으로 연속 3번 이동을 못하게하면 조금의 시간이 단축되지만 효율적이지 않아서 수행하지 않았다.

배열이 이동하는 것은 up방향에만 설명을 했지만, 다른 방향으로 이동하는 것은 반복문의 i, j값만 바뀌기에 up만 이해한다면 다른 방향으로의 이동도 이해할 수 있을꺼라 생각함.

코드

import java.io.*;
import java.util.*;

public class Main {
	static int n, ans;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine());
		int [][] arr = new int[n][n];
		for(int i=0;i<n;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++)
				arr[i][j]=Integer.parseInt(st.nextToken());
		}
		call(0,arr);
		System.out.println(ans);
	}
	
	// 모든 브루트포스 방식으로 모든 방법을 call하면서 경우의 수를 계산
	public static void call(int depth, int[][] arr) {
		if(depth==5)	// 최대 5번만 움직임
			return;
		int [][] brr = copy(arr);	// 각 배열마다 전에 있던 형태 그대로 찾아야 하기에, 계속해서 전의 배열 상태를 복사
		up(brr);	// 위로 올리는 동작
		call(depth+1, brr);	// 위로 올리는 동작 후 다시 call를 호출하여 상하좌우를 탐색
		brr = copy(arr);	// up 함수에서 brr이 바뀌었으므로 다시 brr에 arr의 값을 복사
		down(brr);	// 밑으로 내리는 동작
		call(depth+1, brr);
		brr = copy(arr);
		left(brr);
		call(depth+1, brr);
		brr = copy(arr);
		right(brr);
		call(depth+1, brr);
	}
	
	public static int[][] copy(int [][] arr){	// 매개변수로 들어오는 arr을 brr로 복사하여 brr을 반환
		int[][] brr = new int[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++)
				brr[i][j]=arr[i][j];
		}
		return brr;
	}
	
	public static void up(int [][]arr) {	// 올리는 동작
		for(int j=0;j<n;j++) {	// 위로 올리는 동작은 열을 고정하고 행을 먼저 증가
			int prev=0, prei=0;	// prev = 합쳐지는 값을 확인하기 위한 연속하는 값 확인, prei = prev의 위치 정보를 저장
			for(int i=0;i<n;i++)	// 행을 계속적으로 증가
				if(arr[i][j]!=0){	// 탐색하는 값이 0이 아니라면 합쳐질 수 있는 가능성이 있는 값임
					if(prev==arr[i][j]) {	// 이전에 나온 값과 동일한게 하나 더 나온다면 
						arr[prei][j]=0;	// 전에 있는 값은 0으로 만들고
						arr[i][j]*=2;	// 현재 위치의 값을 2배 올림
						prev=prei=0;	// 값이 변화했기에 전에 있는 값은 존재 하지 않음, 문제에서 동시에 두번이 합쳐질 수 없다고 명시됨
					}
					else {		// 현재값과 이전값이 다르면 새로운 값으로 업데이트
						prev=arr[i][j];
						prei=i;
					}
				}
			int pos=0;	// 공백을 없애기 위한 자리
			for(int i=0;i<n;i++) {
				if(arr[i][j]!=0) {	// 값이 0이 아니면 위로 붙여야 하기에 탐색
					ans=Math.max(ans, arr[i][j]);	// 만들 수 있는 최대 값을 저장 => 최종 정답이 될 값임
					int temp=arr[i][j];	// 현재 위치에 있는 값을 저장하고
					arr[i][j]=0;	// 현재 위치의 값을 0으로 삭제
					arr[pos++][j]=temp;	// 첫자리부터 값을 차곡차곡 저장한다.
				}
			}
		}
	}
	
	public static void down(int [][] arr) {
		for(int j=0;j<n;j++) {
			int prev=0, prei=0;
			for(int i=n-1;i>=0;i--)
				if(arr[i][j]!=0){
					if(prev==arr[i][j]) {
						arr[prei][j]=0;
						arr[i][j]*=2;
						prev=prei=0;
					}
					else {
						prev=arr[i][j];
						prei=i;
					}
				}
			int pos=n-1;
			for(int i=n-1;i>=0;i--) {
				if(arr[i][j]!=0) {
					ans=Math.max(ans, arr[i][j]);
					int temp=arr[i][j];
					arr[i][j]=0;
					arr[pos--][j]=temp;
				}
			}
		}
	}
	
	public static void left(int [][] arr) {
		for(int i=0;i<n;i++) {
			int prev=0, prej=0;
			for(int j=0;j<n;j++)
				if(arr[i][j]!=0){
					if(prev==arr[i][j]) {
						arr[i][prej]=0;
						arr[i][j]*=2;
						prev=prej=0;
					}
					else {
						prev=arr[i][j];
						prej=j;
					}
				}
			int pos=0;
			for(int j=0;j<n;j++) {
				if(arr[i][j]!=0) {
					ans=Math.max(ans, arr[i][j]);
					int temp=arr[i][j];
					arr[i][j]=0;
					arr[i][pos++]=temp;
				}
			}
		}
	}
	
	public static void right(int [][] arr) {
		for(int i=0;i<n;i++) {
			int prev=0, prej=0;
			for(int j=n-1;j>=0;j--)
				if(arr[i][j]!=0){
					if(prev==arr[i][j]) {
						arr[i][prej]=0;
						arr[i][j]*=2;
						
						prev=prej=0;
					}
					else {
						prev=arr[i][j];
						prej=j;
					}
				}
			int pos=n-1;
			for(int j=n-1;j>=0;j--) {
				if(arr[i][j]!=0) {
					ans=Math.max(ans, arr[i][j]);
					int temp=arr[i][j];
					arr[i][j]=0;
					arr[i][pos--]=temp;
				}
			}
		}
	}	
}