[ 알고리즘 ] 코딩 - 백준 12100 - 2048(Easy).java

---

문제 링크

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

---

문제 개요

BOJ 12100 - (자바) 2048(Easy) - 시뮬레이션 / 구현 / 완전 탐색

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

아래 그림은 위로 이동 -> 왼쪽 이동을 한 모습이다.

이동 예시

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

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

---

로직

Step 01. 일반적인 순열을 이용해서 선택할 수 있는 경우를 모두 검사할 것이다. 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력하므로, 5개까지 선택하고 이동시킨다.

Step 02. Step01에서 선택된 방향을 기준으로 맵을 이동시키자. 각 방향마다 인덱스 관리를 잘해야 한다. 머리가 지끈지끈 하지만 눈 크게 뜨고 작성하자! 우선 처음 위치의 숫자를 확인한다. 0이라면 다음에 자신이 위치하게 될 인덱스(sum_idx)를 -1로 0이 아니라면 0으로 초기화 해주자. 

초기 모양

두 숫자가 다르면 이전 값(pre)에 현재 값(cur)을 넣어주고 현재 값의 위치를 0으로 바꾼다. 이때 자신이 가야 할 위치를 알려주는 인덱스가 sum_idx이고, 이 위치로 cur 값을 옮겨준다. ( 중간에 0이 있어도 제자리를 찾아갈 수 있게 해 준다)

두 숫자 다를 때 로직 

두 숫자가 같다면 이전 숫자의 위치(sum_idx)에 pre+cur값을 넣어주고 현재 위치는 0으로 pre는 0으로 바꾸어 준다.

두 숫자 같을 때 로직

Step 03. Step 02에서 나온 최댓값과 이전 최댓값을 비교해서 더 큰 값을 저장한다.

Step 04. 모든 과정을 마치고 최후에 저장된 최댓값이 정답!

 

분명 다른 방법이 있겠지만 생각한 방법이 이 방법이라 이런 식으로 구현했지만.. 인덱스에 정신이 멍해지면 틀리기 일쑤일 것 같은 문제였다.

---

코드

/**
 * 
 */
package samsung_test;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * @author YSM
 *
 */
public class BOJ_12100_2048 {
	private static int MAX;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		int[][] map = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer stt = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(stt.nextToken());
			}
		} // input end

		int[] selected = new int[5];
		process(0, map, N, selected);
		System.out.println(MAX);
	}

	private static void process(int idx, int[][] map, int n, int[] selected) {
		if (idx == 5) { // 5번 이동
			// 선택 한 방향을 기준으로 숫자를 이동시키자
			int res = move_map(selected, map, n);
			MAX = MAX > res ? MAX : res; // 최대치 갱신
			return;
		}
		for (int d = 0; d < 4; d++) {
			selected[idx] = d; // 방향 선택
			process(idx + 1, map, n, selected);
		}
	}

	private static int move_map(int[] selected, int[][] map, int n) {
		// 복사된 맵으로 이동 시킬 것이다!
		int[][] init_map = new int[n][n];
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				init_map[i][j] = map[i][j];
			}
		}

		// 각 방향에 따라 이동
		for (int dir : selected) {
			switch (dir) {
			case 0: // 위쪽
				move_up(init_map, n);
				break;
			case 1: // 아래쪽
				move_down(init_map, n);
				break;
			case 2: // 왼쪽
				move_left(init_map, n);
				break;
			case 3: // 오른쪽
				move_right(init_map, n);
				break;
			}
		}
		
		// 최대 치 산출
		int max = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int cur = init_map[i][j];
				max = max > cur ? max : cur;
			}
		}
		return max;
	}
	
	// 오른쪽 이동
	private static void move_right(int[][] init_map, int n) {
		for(int i = 0; i < n; i++) {
			int pre = init_map[i][n - 1];
			int sum_idx = pre == 0 ? n : n - 1;
			for (int j = n-2; j >= 0; j--) {
				int cur = init_map[i][j];
				if (cur == 0)
					continue;
				if (pre != cur) {
					sum_idx--;
					pre = cur;
					init_map[i][j] = 0;
					init_map[i][sum_idx] = cur;
				} else {
					init_map[i][sum_idx] = pre + cur;
					init_map[i][j] = 0;
					pre = 0;
				}
			}
		}
	}
	
	// 왼쪽 이동
	private static void move_left(int[][] init_map, int n) {
		for(int i = 0; i < n; i++) {
			int pre = init_map[i][0];
			int sum_idx = pre == 0 ? -1 : 0;
			for (int j = 1; j < n; j++) {
				int cur = init_map[i][j];
				if (cur == 0)
					continue;
				if (pre != cur) {
					sum_idx++;
					pre = cur;
					init_map[i][j] = 0;
					init_map[i][sum_idx] = cur;
				} else {
					init_map[i][sum_idx] = pre + cur;
					init_map[i][j] = 0;
					pre = 0;
				}
			}
		}
	}
	
	// 밑으로 이동
	private static void move_down(int[][] init_map, int n) {
		for(int j = 0; j < n; j++) {
			int pre = init_map[n-1][j];
			int sum_idx = pre == 0 ? n : n-1;
			for (int i = n-2; i >= 0; i--) {
				int cur = init_map[i][j];
				if (cur == 0)
					continue;
				if (pre != cur) {
					sum_idx--;
					pre = cur;
					init_map[i][j] = 0;
					init_map[sum_idx][j] = cur;
				} else {
					init_map[sum_idx][j] = pre + cur;
					init_map[i][j] = 0;
					pre = 0;
				}
			}
		}
	}

	// 위로 이동
	private static void move_up(int[][] init_map, int n) {
		for(int j = 0; j < n; j++) {
			int pre = init_map[0][j];
			int sum_idx = pre == 0 ? -1 : 0;
			for (int i = 1; i < n; i++) {
				int cur = init_map[i][j];
				if (cur == 0)
					continue;
				if (pre != cur) {
					sum_idx++;
					pre = cur;
					init_map[i][j] = 0;
					init_map[sum_idx][j] = cur;
				} else {
					init_map[sum_idx][j] = pre + cur;
					init_map[i][j] = 0;
					pre = 0;
				}
			}
		}
	}
}