백준 12100 (2048(Easy))

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

문제가 길어서 직접 읽어보는 것이 좋겠다.

 

 

 

 

풀이

---

중복순열로 완전탐색을 해서 풀수도 있지만, 순열을 하나씩 만들어서 푸는 방법보다 DFS 로 하나씩 완전탐색하는 방식이 더욱 편할 것 같아 DFS로 풀었다.

 

DFS로 오른쪽 왼쪽 위 아래 순서대로 밀었을때의 값을 저장하고 모든 방법을 돌리면,

4^5의 가짓수가 나온다. 이를 이용하여 풀면된다.

전형적인 시뮬레이션 문제다.

 

static void dfs(int[][] cube, int count) {
	
	if(count > 5) {
		return;
	}
	answer = findMax(cube, answer);

	for(int i = 0 ; i < 4 ; i++) {
		int[][] copy = new int[n][n];
		for(int j = 0 ; j < n ; j++) {
			copy[j] = cube[j].clone();
		}
		
		int[][] change_cube = move_Cube(copy, i);
		dfs(change_cube, count + 1);
	}
		
}

DFS로 모든 방향을 하나씩 넣어준다.

이 때, copy[] 배열을 만들어 처음의 cube 가 변하지 않게 해준다.

 

각 값을 4가지 방향으로 합치는 방식은 queue를 사용해서 구현하였다.

하나를 통해 코드를 설명하면,

for(int i = 0 ; i < n ; i++) {
				
	for(int j = n - 1 ; j >= 0 ; j--) {
		if(cube[i][j] != 0) {
			queue.add(cube[i][j]);
			cube[i][j] = 0;
		}
	}
				
	int j = n -1;
	while(!queue.isEmpty()) {
		int front = queue.poll();
				
		if(cube[i][j] == 0) {
			cube[i][j] = front;
		}
		else {
			if(front == cube[i][j]) {
				cube[i][j] += front;
				j--;
			}
			else {
				j--;
				cube[i][j] = front;
			}
		}
	}
}	

오른쪽으로 미는것을 표현한 코드다.

오른쪽으로 민다는것을 오른쪽부터 값을 queue에 넣어준다.

queue의 값을 하나씩 뽑으며 때, 해당 값이 연속되는지 아닌지를 판단하여 다시 값을 채워준다.

 

 

<전체코드>

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

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	
	static int answer = 0;
	static int n;
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(bufferedReader.readLine());
		
		int[][] cube = new int[n][n];
		
		for(int i = 0 ; i < n ; i++) {
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			for(int j = 0 ; j < n ; j++) {
				cube[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dfs(cube, 0);
		
		System.out.println(answer);
	}
	
	static int[][] move_Cube(int[][] cube, int direct){
		
		Queue<Integer> queue = new LinkedList<Integer>();
				
		switch(direct) {
		
		case 0 :
			for(int i = 0 ; i < n ; i++) {
				
				for(int j = n - 1 ; j >= 0 ; j--) {
					if(cube[i][j] != 0) {
						queue.add(cube[i][j]);
						cube[i][j] = 0;
					}
				}
				
				int j = n -1;
				while(!queue.isEmpty()) {
					int front = queue.poll();
					
					if(cube[i][j] == 0) {
						cube[i][j] = front;
					}
					else {
						if(front == cube[i][j]) {
							cube[i][j] += front;
							j--;
						}
						else {
							j--;
							cube[i][j] = front;
						}
					}
				}
			}		
			
			break;
			
		case 1:
			for(int i = 0 ; i < n ; i++) {
				for(int j = 0 ; j < n ; j++) {
					if(cube[i][j] != 0) {
						queue.add(cube[i][j]);
						cube[i][j] = 0;
					}
				}
				
				int j = 0;
				while(!queue.isEmpty()) {
					int front = queue.poll();
					
					if(cube[i][j] == 0) {
						cube[i][j] = front;
					}
					else {
						if(front == cube[i][j]) {
							cube[i][j] += front;
							j++;
						}
						else {
							j++;
							cube[i][j] = front;
						}
					}
				}
			}
			break;
			
		case 2:
			
			for(int i =  0 ; i < n ; i++) {
				
				for(int j = n - 1 ; j >= 0 ; j--) {
					if(cube[j][i] != 0) {
						queue.add(cube[j][i]);
						cube[j][i] = 0;
					}
				}
				
				int j = n - 1;
				while(!queue.isEmpty()) {
					
					int front = queue.poll();
					
					if(cube[j][i] == 0) {
						cube[j][i] = front;
					}
					else {
						if(cube[j][i] == front) {
							cube[j][i] += front;
							j--;
						}
						else {
							j--;
							cube[j][i] = front;
						}
					}
				}
			}
			break;
			
		case 3:
			for(int i = 0 ; i < n ; i++) {
				for(int j = 0 ; j < n ; j++) {
					
					if(cube[j][i] != 0) {
						queue.add(cube[j][i]);
						cube[j][i] = 0;
					}
				}
				
				int j = 0;
				while(!queue.isEmpty()) {
					int front = queue.poll();
					
					if(cube[j][i] == 0) {
						cube[j][i] = front;
					}
					else {
						if(cube[j][i] == front) {
							cube[j][i] += front;
							j++;
						}
						else {
							j++;
							cube[j][i] = front;
						}
					}
				}
			}
			
			break;
		}		
		return cube;
	}
	
	static int findMax(int[][] cube, int answer) {
		
		int max = 0;
		
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < n ; j++) {
				max = Math.max(max, cube[i][j]);
			}
		}
		
		return Math.max(max, answer);
	}
	
	
	static void dfs(int[][] cube, int count) {
		
		if(count > 5) {
			return;
		}
		answer = findMax(cube, answer);
		
		for(int i = 0 ; i < 4 ; i++) {
			int[][] copy = new int[n][n];
			for(int j = 0 ; j < n ; j++) {
				copy[j] = cube[j].clone();
			}
			
			int[][] change_cube = move_Cube(copy, i);
			dfs(change_cube, count + 1);
		}
		
	}
}