2048(Easy)

🔗문제 링크

구현 코드

import java.util.*;

public class Solution {
	static int n;
	static int[][] board;
	static int answer = 0;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		board = new int[n][n];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				board[i][j] = in.nextInt();
			}
		}

		dfs(0);

		System.out.println(answer);
		
		in.close();

	}

	static void dfs(int count) {
		if (count == 5) {
			findMax();
			return;	
		} 

		
		 int[][] copy = new int[n][n];
		 for(int i = 0; i < n; i++)
	            copy[i] = board[i].clone();
		 //이차원배열은 clone으로 깊은 복사 안됨 
		 
		for(int dir=0;dir<4;dir++) {
			move(dir);
			dfs(count+1);
			 for(int i = 0; i < n; i++)
	                board[i] = copy[i].clone();
		}
		
	}
	
	static void move(int dir) {
		if(dir == 0) {
			//상 
			for(int i=0;i<n;i++) { 
				int index = 0; //합치고 블록 둘 위치
				int block = 0;
				for(int j=0;j<n;j++) { 
					if(board[j][i]!=0) {
						if(block == board[j][i]) {
							board[index-1][i] = block*2;
							block = 0;
							board[j][i] = 0;
						}
						else {
							block = board[j][i];
							board[j][i] = 0;
							board[index++][i] = block;
						}
					}
				}
			}
			
		}
		else if(dir == 1) {
			//하 
			for(int i=0;i<n;i++) { 
				int index = n-1; 
				int block = 0;
				for(int j=n-1;j>=0;j--) { 
					if(board[j][i]!=0) {
						if(block == board[j][i]) {
							board[index+1][j] = block*2;
							block = 0;
							board[j][i] = 0;
						}
						else {
							block = board[j][i];
							board[j][i] = 0;
							board[index--][i] = block;
						}
					}
				}
			}
			
		}
		else if(dir == 2) {
			//좌 
			for(int i=0;i<n;i++) { 
				int index = 0; 
				int block = 0;
				for(int j=0;j<n-1;j++) { 
					if(board[i][j]!=0) {
						if(block == board[i][j]) {
							board[i][index-1] = block*2;
							block = 0;
							board[i][j] = 0;
						}
						else {
							block = board[i][j];
							board[i][j] = 0;
							board[i][index++] = block;
						}
					}
				}
			}
		
		}
		else {
			//우 
			for(int i=0;i<n;i++) { 
				int index = n-1; //합치고 블록 둘 위치
				int block = 0;
				for(int j=n-1;j>=0;j--) { 
					if(board[i][j]!=0) {
						if(block == board[i][j]) {
							board[i][index+1] = block*2;
							block = 0;
							board[i][j] = 0;
						}
						else {
							block = board[i][j];
							board[i][j] = 0;
							board[i][index--] = block;
						}
					}
				}
			}
			
		}
			
	}

	static void findMax() {
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				answer = Math.max(answer,board[i][j]);
			}
		}
	}
}

• 알고리즘

  dfs(int count) : count횟수 검사 -> 5일 경우 max값 찾기
  5가 아닌 경우에는 4방향에 대해서 2048 게임 수행
  이때 각 방향에 대해서 원본배열을 똑같이 유지해줘야 하므로 배열복사 후 복사한 배열로 게임 수행

전형적인 dfs 문제였는데 처음에 각 방향별로 배열을 같게 넣어줘야하는데 이부분을 어떻게 처리할지 감이 안왔음 .. 복사해서 수행하면 되는 것을.. ㅠ
그리고 상하좌우 이동 자체도 값을 저장하고 처리하는 과정이 필요해서 이해가 어려웠음.. 다음번에 다시 풀때는 혼자 힘으로 풀 수 있길..

참고

2048(Easy)