[백준 12100] 2048 (Easy) (자바)

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

난이도 : 골드 2

 

난이도에 비해 어렵지 않은 문제였습니다.

백트래킹으로 구현을 하면 풀 수 있습니다.

 

총 5번의 이동으로 가장 큰 수를 구해야 하므로 각 이동(상, 하, 좌, 우)을 백트래킹을 이용해 구현했습니다.

 

---

전역 변수 

n = 맵의 크기

answer = 5번의 이동이 끝났을 때의 가장 큰 값

map = 게임 판

메소드

void main 

입력을 받고 게임을 시작한 후 answer를 출력합니다.

(game 호출)

 

void game

총 5번의 동작을 합니다.

매 동작 전 백트래킹이 가능하도록 map을 copy 배열에 복사해둡니다.

동작 후 재귀가 끝났을 때 copy배열의 값을 map으로 불러와 기존 값을 복구합니다.

 

void move

dir의 값에 따라 동작을 달리합니다.

0 - 상, 1 - 하, 2 - 좌, 3 - 우입니다.

index는 값을 넣을 위치를 가리키고, block은 최근 블록의 수를 저장합니다.

 

2 2 4 0을 위로 몰아넣는 동작 과정을 그림으로 나타낸 것입니다.

 

void findMax

map을 순회하며 가장 큰 수를 찾아냅니다.

 

 

	import java.io.BufferedReader;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class p12100 {
	static int n, answer, map[][];
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	n = Integer.parseInt(br.readLine());
	answer = 0;
	map = new int[n][n];
	StringTokenizer stz;
	for(int i = 0; i < n; i++) {
	stz = new StringTokenizer(br.readLine());
	for(int j = 0; j < n; j++)
	map[i][j] = Integer.parseInt(stz.nextToken());
	}
	game(0);
	System.out.println(answer);
	}
	public static void game(int count) {
	if(count == 5) {
	findMax();
	return;
	}
	int copy[][] = new int[n][n];
	for(int i = 0; i < n; i++)
	copy[i] = map[i].clone();
	for(int i = 0; i < 4; i++) {
	move(i);
	game(count+1);
	for(int a = 0; a < n; a++)
	map[a] = copy[a].clone();
	}
	}
	public static void move(int dir) {
	switch(dir) {
	//위로 몰기
	case 0:
	for(int i = 0; i < n; i++) {
	int index = 0;
	int block = 0;
	for(int j = 0; j < n; j++) {
	if(map[j][i] != 0) {
	if(block == map[j][i]) {
	map[index - 1][i] = block * 2;
	block = 0;
	map[j][i] = 0;
	}
	else {
	block = map[j][i];
	map[j][i] = 0;
	map[index][i] = block;
	index++;
	}
	}
	}
	}
	break;
	//왼쪽으로 몰기
	case 1:
	for(int i = 0; i < n; i++) {
	int index = n - 1;
	int block = 0;
	for(int j = n - 1; j >= 0; j--) {
	if(map[j][i] != 0) {
	if(block == map[j][i]) {
	map[index + 1][i] = block * 2;
	block = 0;
	map[j][i] = 0;
	}
	else {
	block = map[j][i];
	map[j][i] = 0;
	map[index][i] = block;
	index--;
	}
	}
	}
	}
	break;
	//왼쪽으로 몰기
	case 2:
	for(int i = 0; i < n; i++) {
	int index = 0;
	int block = 0;
	for(int j = 0; j < n; j++) {
	if(map[i][j] != 0) {
	if(block == map[i][j]) {
	map[i][index - 1] = block * 2;
	block = 0;
	map[i][j] = 0;
	}
	else {
	block = map[i][j];
	map[i][j] = 0;
	map[i][index] = block;
	index++;
	}
	}
	}
	}
	break;
	//오른쪽으로 몰기
	case 3:
	for(int i = 0; i < n; i++) {
	int index = n - 1;
	int block = 0;
	for(int j = n - 1; j >= 0; j--) {
	if(map[i][j] != 0) {
	if(block == map[i][j]) {
	map[i][index + 1] = block * 2;
	block = 0;
	map[i][j] = 0;
	}
	else {
	block = map[i][j];
	map[i][j] = 0;
	map[i][index] = block;
	index--;
	}
	}
	}
	}
	break;
	}
	}
	public static void findMax() {
	for(int i = 0; i < n; i++)
	for(int j = 0; j < n; j++)
	answer = Math.max(answer, map[i][j]);
	}
	}

view raw p12100.java hosted with ❤ by GitHub