알고리즘/백준
[BOJ] 12100 - 2048 (Easy) (Java)
DeveloperJason
2023. 8. 17. 11:15
접근법
진짜 빡구현이란 이런 것이다..
디버깅이 헬이었던 문제
최적화가 필요할 것 같다
참고한 테스트케이스 첨부하겠음
#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 |