[BOJ] 12100 - 2048 (Easy) (Java)

접근법

진짜 빡구현이란 이런 것이다..

디버깅이 헬이었던 문제

최적화가 필요할 것 같다

참고한 테스트케이스 첨부하겠음

#TC 1
input:
4
2 16 16 0
32 16 4 1
4 16 32 0
2 0 8 8

correct answer: 128
output: 64

#TC 2
input:
4
0 8 1 1
8 0 1 4
8 0 8 32
1 32 32 0

correct answer: 128
output: 64

#TC 3
input:
4
2 32 16 8
4 0 4 4
0 1 8 4
32 32 0 32

correct answer: 64
output: 128

---

코드

package boj;

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

public class BOJ_12100_2048_Easy {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int max_cnt = 0;
	static int N;

	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		int[][] board = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		game(board, 0, 0);
		System.out.println(max_cnt);

	}

	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };

	public static void game(int[][] board, int cnt, int idx) {

		int[][] t_board = board.clone();
		for (int i = 0; i < N; i++) {
			t_board[i] = board[i].clone();
		}

		if (cnt == 5) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					max_cnt = Math.max(max_cnt, board[i][j]);
				}
			}
			return;
		}

		// 먼저 이동한 애들을 확인해야하는데..
		for (int d = 0; d < 4; d++) {
			boolean[][] sumChecker = new boolean[N][N];
			int nx = dx[d];
			int ny = dy[d];
			switch (d) {
			case 0:
				// 왼쪽
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						int t_i = i;
						int t_j = j;
						// 이동할 때 원래 자리에 0 을 집어넣고 이동, 벽이 아닌 다른 숫자가 나왔을 때
						// 그 숫자가 같은 숫자면 합치고 현재 위치는 0
						if (board[i][j] == 0) // 0이면 굳이 확인할 필요 없다.
							continue;
						while (0 <= i + nx && i + nx < N && 0 <= j + ny && j + ny < N) {
							if (board[i + nx][j + ny] == 0) {
								board[i + nx][j + ny] = board[i][j]; // 이동하려는 위치에 현재 값을 넣음
								board[i][j] = 0;
							}

							else if (board[i + nx][j + ny] == board[i][j] && !sumChecker[i + nx][j + ny]) {
								// 합쳐야하긴하는데 한번 합쳐진애는 합치면 안돼
								// 한번 합쳤는지 아닌지를 어떻게 알까
								// checker에 좌표를 저장해두자

								board[i + nx][j + ny] += board[i][j];// 원래 있던 애 합치고
								board[i][j] = 0; // 0으로 만듦
								sumChecker[i + nx][j + ny] = true;
								// 여기까지 왔으면 사실 더 이상 이동할 수 없음
								break;

							} else {
								break; // 아무곳도 이동 못할 때 탈출
							}
							i += nx; // 좌표 이동
							j += ny; // 좌표 이동

						}
						i = t_i;
						j = t_j;

					}
				}

				break;
			case 1:
				// 오른쪽 부터 확인해야 한다.

				for (int i = 0; i < N; i++) {
					for (int j = N - 1; j >= 0; j--) {
						int t_i = i;
						int t_j = j;
						// 이동할 때 원래 자리에 0 을 집어넣고 이동, 벽이 아닌 다른 숫자가 나왔을 때
						// 그 숫자가 같은 숫자면 합치고 현재 위치는 0
						if (board[i][j] == 0) // 0이면 굳이 확인할 필요 없다.
							continue;
						while (0 <= i + nx && i + nx < N && 0 <= j + ny && j + ny < N) {
							if (board[i + nx][j + ny] == 0) {
								board[i + nx][j + ny] = board[i][j]; // 이동하려는 위치에 현재 값을 넣음
								board[i][j] = 0;
							}

							else if (board[i + nx][j + ny] == board[i][j] && !sumChecker[i + nx][j + ny]) {
								// 합쳐야하긴하는데 한번 합쳐진애는 합치면 안돼
								// 한번 합쳤는지 아닌지를 어떻게 알까
								// checker에 좌표를 저장해두자

								board[i + nx][j + ny] += board[i][j];// 원래 있던 애 합치고
								board[i][j] = 0; // 0으로 만듦
								sumChecker[i + nx][j + ny] = true;
								// 여기까지 왔으면 사실 더 이상 이동할 수 없음
								break;
							} else {
								break; // 아무곳도 이동 못할 때 탈출
							}
							i += nx; // 좌표 이동
							j += ny; // 좌표 이동

						}

						i = t_i;
						j = t_j;

					}
				}

				break;
			case 2:
				// 위쪽

				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						int t_i = i;
						int t_j = j;
						// 이동할 때 원래 자리에 0 을 집어넣고 이동, 벽이 아닌 다른 숫자가 나왔을 때
						// 그 숫자가 같은 숫자면 합치고 현재 위치는 0
						if (board[i][j] == 0) // 0이면 굳이 확인할 필요 없다.
							continue;
						while (0 <= i + nx && i + nx < N && 0 <= j + ny && j + ny < N) {
							if (board[i + nx][j + ny] == 0) {
								board[i + nx][j + ny] = board[i][j]; // 이동하려는 위치에 현재 값을 넣음
								board[i][j] = 0;
							}

							else if (board[i + nx][j + ny] == board[i][j] && !sumChecker[i + nx][j + ny]) {
								// 합쳐야하긴하는데 한번 합쳐진애는 합치면 안돼
								// 한번 합쳤는지 아닌지를 어떻게 알까
								// checker에 좌표를 저장해두자

								board[i + nx][j + ny] += board[i][j];// 원래 있던 애 합치고
								board[i][j] = 0; // 0으로 만듦
								sumChecker[i + nx][j + ny] = true;
								// 여기까지 왔으면 사실 더 이상 이동할 수 없음
								break;
							} else {
								break; // 아무곳도 이동 못할 때 탈출
							}
							i += nx; // 좌표 이동
							j += ny; // 좌표 이동

						}

						i = t_i;
						j = t_j;

					}
				}

				break;
			case 3:
				// 아래쪽 // x가 커진다. // 큰 수부터 이동하는걸 확인해야해

				for (int i = N - 1; i >= 0; i--) {
					for (int j = 0; j < N; j++) {
						int t_i = i;
						int t_j = j;
						// 이동할 때 원래 자리에 0 을 집어넣고 이동, 벽이 아닌 다른 숫자가 나왔을 때
						// 그 숫자가 같은 숫자면 합치고 현재 위치는 0
						if (board[i][j] == 0) // 0이면 굳이 확인할 필요 없다.
							continue;
						while (0 <= i + nx && i + nx < N && 0 <= j + ny && j + ny < N) {
							if (board[i + nx][j + ny] == 0) {
								board[i + nx][j + ny] = board[i][j]; // 이동하려는 위치에 현재 값을 넣음
								board[i][j] = 0;
							}

							else if (board[i + nx][j + ny] == board[i][j] && !sumChecker[i + nx][j + ny]) {
								// 합쳐야하긴하는데 한번 합쳐진애는 합치면 안돼
								// 한번 합쳤는지 아닌지를 어떻게 알까
								// checker에 좌표를 저장해두자

								board[i + nx][j + ny] += board[i][j];// 원래 있던 애 합치고
								board[i][j] = 0; // 0으로 만듦
								sumChecker[i + nx][j + ny] = true;
								// 여기까지 왔으면 사실 더 이상 이동할 수 없음
								break;
							} else {
								break; // 아무곳도 이동 못할 때 탈출
							}
							i += nx; // 좌표 이동
							j += ny; // 좌표 이동

						}

						i = t_i;
						j = t_j;

					}
				}

				break;

			}

			game(board, cnt + 1, idx + 1);
			for (int i = 0; i < N; i++) {
				board[i] = t_board[i].clone();
			}
		}
	}
}

결과

메모리 시간 언어

28892KB

452ms

Java