[java] 백준(BOJ) - 2048(Easy)

문제

백준-2048(Easy)
2048게임에서 최대 5번 이동 후 만들 수 있는 가장 큰 블록의 값을 구하는 문제

• 제한 사항
  보드의 크기 N : 1 <= N <= 20
  블록의 쓰인 수 : 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴

풀이

5회 이동 후 만들 수 있는 가장 큰 블록을 구해야 하므로 최대 5회까지 진행을 해야한다
dfs를 사용했고, 상(0), 하(1), 좌(2), 우(3) 값을 사용해서 배열을 이동시켰다

초기 0회일때는 입력받을 때 구해야하는 max값을 갱신했으므로,
0회가 아닐때 max를 확인한다

배열 이동 시 deep copy, shallow copy 주의하기 !

시행착오

1. 이동 주의
   이 문제에서 어려운 것은 이동하는 부분이다(ㅠㅠ)
   예를 들어 [2,2,4,0]인 경우 좌로 이동한다고 하면
   [8,0,0,0]이 아닌, [4,4,0,0]이다
   문제 조건에 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이라고 나와있다
   • [2,2,2,2]를 왼쪽으로 밀기, 결과: [4,4,0,0]
   • [4,4,8,8]를 왼쪽으로 밀기, 결과: [8,16,0,0]
     역시나 반성.. 문제 꼼꼼히 읽기…
2. 이동 방향 지정
   상으로 밀은 배열을 또 한번 상으로 밀면 결과가 같을 것이라고 생각해서 진행하지 않았다
   이 결과 73%즈음에서 틀림
   1의 문제조건처럼 이미 합친블록은 또 합칠 수 없기 때문에
   한번 더 같은 방향으로 밀 경우, 다른 결과가 나올 수 있다
   • [2,2,2,2]를 왼쪽으로 밀기, 결과: [4,4,0,0]
   • [4,4,0,0]를 왼쪽으로 밀기, 결과: [8,0,0,0]

소스코드

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

public class b12100_2048easy {

	private static int N;
	static int max;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		int[][] map = new int[N][N];
		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				max = Math.max(max, map[i][j]);
			}
		}
		// 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값
		dfs(clone(map), 0);
		System.out.println(max);
	}

	private static void dfs(int[][] arr, int cnt) {
		if (cnt != 0)
			findMax(arr);
		if (cnt == 5) {
			return;
		}
		for (int i = 0; i < 4; i++) {
			dfs(arrange(arr, i), cnt + 1);
		}
	}

	private static int[][] arrange(int[][] arr, int dir) {
		int tmp[][] = clone(arr);
		switch (dir) {
		case 0: // 상
			for (int c = 0; c < N; c++) {
				int r = 0;
				while (r < N - 1) {
					int k = r + 1;
					while (k + 1 < N && tmp[k][c] == 0) {
						k++;
					}
					if (tmp[k][c] == 0) {
						r++;
						continue;
					}
					if (tmp[r][c] == 0) {
						tmp[r][c] = tmp[k][c];
						tmp[k][c] = 0;
						continue;
					} else if (tmp[r][c] == tmp[k][c]) {
						tmp[r][c] *= 2;
						tmp[k][c] = 0;
					} else if (tmp[r][c] != tmp[k][c] && k != r + 1) {
						tmp[r + 1][c] = tmp[k][c];
						tmp[k][c] = 0;
					}
					r++;
				}
			}
			break;
		case 1: // 하
			for (int c = 0; c < N; c++) {
				int r = N - 1;
				while (r > 0) {
					int k = r - 1;
					while (k - 1 > -1 && tmp[k][c] == 0) {
						k--;
					}
					if (tmp[k][c] == 0) {
						r--;
						continue;
					}
					if (tmp[r][c] == 0) {
						tmp[r][c] = tmp[k][c];
						tmp[k][c] = 0;
						continue;
					} else if (tmp[r][c] == tmp[k][c]) {
						tmp[r][c] *= 2;
						tmp[k][c] = 0;
					} else if (tmp[r][c] != tmp[k][c] && k != r - 1) {
						tmp[r - 1][c] = tmp[k][c];
						tmp[k][c] = 0;
					}
					r--;
				}
			}
			break;
		case 2: // 좌
			for (int r = 0; r < N; r++) {
				int c = 0;
				while (c < N - 1) {
					int k = c + 1;
					while (k + 1 < N && tmp[r][k] == 0) {
						k++;
					}
					if (tmp[r][k] == 0) {
						c++;
						continue;
					}
					if (tmp[r][c] == 0) {
						tmp[r][c] = tmp[r][k];
						tmp[r][k] = 0;
						continue;
					} else if (tmp[r][c] == tmp[r][k]) {
						tmp[r][c] *= 2;
						tmp[r][k] = 0;
					} else if (tmp[r][c] != tmp[r][k] && k != c + 1) {
						tmp[r][c + 1] = tmp[r][k];
						tmp[r][k] = 0;
					}
					c++;
				}
			}
			break;
		case 3: // 우
			for (int r = 0; r < N; r++) {
				int c = N - 1;
				while (c > 0) {
					int k = c - 1;
					while (k - 1 > -1 && tmp[r][k] == 0) {
						k--;
					}
					if (tmp[r][k] == 0) {
						c--;
						continue;
					}
					if (tmp[r][c] == 0) {
						tmp[r][c] = tmp[r][k];
						tmp[r][k] = 0;
						continue;
					} else if (tmp[r][c] == tmp[r][k]) {
						tmp[r][c] *= 2;
						tmp[r][k] = 0;
					} else if (tmp[r][c] != tmp[r][k] && k != c - 1) {
						tmp[r][c - 1] = tmp[r][k];
						tmp[r][k] = 0;
					}
					c--;
				}
			}
			break;
		}
		return tmp;
	}

	private static void findMax(int[][] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				max = Math.max(max, arr[i][j]);
			}
		}
	}

	private static int[][] clone(int[][] map) {
		int[][] tmp = new int[N][N];
		for (int i = 0; i < map.length; i++) {
			tmp[i] = map[i].clone();
		}
		return tmp;
	}
}