정답코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int max = Integer.MIN_VALUE;
static int[][] game;
static int[] mode = {1,2,3,4}; //east,west,south,north
static Deque<Integer> dq = new ArrayDeque<>();
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
game = new int[N][N];
for(int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; j++) {
game[i][j] = Integer.parseInt(st.nextToken());
}
}
start(0,game);
System.out.println(max);
}
public static void start(int depth, int[][]play) {
if(depth == 5) {
for(int i = 0; i< N; i++) {
for(int j = 0; j < N; j++) {
if(play[i][j]>max) {
max = play[i][j];
}
}
}
return;
}
for(int dir : mode) {
int [][]copy = new int[N][N];
switch(dir) {
//east
case 1:
//System.out.println("right");
for(int i = 0; i < N; i++) {
//일단 그 행에 대한 배열 초기화 -> 한 쪽으로 밀기 위해서
for(int j = N-1; j>=0 ; j--) {
if(play[i][j]!=0) {
//일단 queue에 넣고
dq.add(play[i][j]);
}
}
//동쪽 끝에서부터 하나씩 추가 if 같은게 있다면 더해준다 & 한 번 합치고 나면 flag = false로 대입
int idx = N-1;
int temp = -1;
while(!dq.isEmpty()) {
//System.out.println(dq);
int now = dq.removeFirst();
//만약 합쳐질 수 있고 이전 값과 지금 값이 같을 경우 합쳐준다
if(temp == now) {
//play[i][idx+1] *= 2;
copy[i][idx+1] *= 2;
temp = -1;
}
//합쳐질 수 없는 case (같거나 다르거나 상관 x )
else {
copy[i][idx] = now;
temp = now;
idx--;
}
}
}
break;
//west
case 2:
//System.out.println("left");
for(int i = 0; i < N; i++) {
//일단 그 행에 대한 배열 초기화 -> 한 쪽으로 밀기 위해서
for(int j = 0; j< N ; j++) {
if(play[i][j]!=0) {
//일단 queue에 넣고
dq.add(play[i][j]);
}
}
//동쪽 끝에서부터 하나씩 추가 if 같은게 있다면 더해준다 & 한 번 합치고 나면 flag = false로 대입
int idx = 0;
int temp = -1;
while(!dq.isEmpty()) {
int now = dq.removeFirst();
//만약 합쳐질 수 있고 이전 값과 지금 값이 같을 경우 합쳐준다
if(temp == now) {
copy[i][idx-1] *= 2;
temp = -1;
}
//합쳐질 수 없는 case (같거나 다르거나 상관 x )
else {
copy[i][idx] = now;
temp = now;
idx++;
}
}
}
break;
//south
case 3:
//System.out.println("down");
for(int i = 0; i < N; i++) {
//일단 그 행에 대한 배열 초기화 -> 한 쪽으로 밀기 위해서
for(int j = N-1; j>=0 ; j--) {
if(play[j][i]!=0) {
//일단 queue에 넣고
dq.add(play[j][i]);
}
}
//동쪽 끝에서부터 하나씩 추가 if 같은게 있다면 더해준다 & 한 번 합치고 나면 flag = false로 대입
int idx = N-1;
int temp = -1;
while(!dq.isEmpty()) {
for(int a = 0; a < N; a++) {
for(int b = 0; b < N; b++) {
}
}
int now = dq.removeFirst();
//만약 합쳐질 수 있고 이전 값과 지금 값이 같을 경우 합쳐준다
if(temp == now) {
copy[idx+1][i] *= 2;
temp = -1;
}
//합쳐질 수 없는 case (같거나 다르거나 상관 x )
else {
copy[idx][i] = now;
temp = now;
idx--;
}
}
}
break;
//north
case 4:
//System.out.println("up");
for(int i = 0; i < N; i++) {
//일단 그 행에 대한 배열 초기화 -> 한 쪽으로 밀기 위해서
for(int j = 0; j < N ; j++) {
if(play[j][i]!=0) {
//일단 queue에 넣고
dq.add(play[j][i]);
}
}
//동쪽 끝에서부터 하나씩 추가 if 같은게 있다면 더해준다 & 한 번 합치고 나면 flag = false로 대입
boolean flag = true;
int idx = 0;
int temp = -1;
while(!dq.isEmpty()) {
int now = dq.removeFirst();
//만약 합쳐질 수 있고 이전 값과 지금 값이 같을 경우 합쳐준다
if(temp == now) {
copy[idx-1][i] *= 2;
temp = -1;
}
//합쳐질 수 없는 case (같거나 다르거나 상관 x )
else {
copy[idx][i] = now;
temp = now;
idx++;
}
}
}
break;
}
start(depth+1,copy);
}
}
}전략
-
최대 5번을 움직인 다음 합쳐진 값의 최댓값을 찾는 문제 → 재귀를 이용해서 depth가 5일 때 Basis 조건으로 잡고 최댓값을 구하자
-
동서남북으로 이동할 수 있지만 결국 인덱스만 달라지고 하나만 구현하면 된다.
-
한 번 합쳐진 블록은 다시 합쳐지면 안 된다 & 제일 먼저 충돌한 2블록이 합쳐진다… 조건을 보았을 때 이전 블록을 다 queue로 뺀다음에 조건에 맞게 하나하나 넣어주는게 낫다고 생각
-
위, 아래로 움직이면 열 기준으로만 배치, 좌,우로 움직일 땐 행 기준으로만 배치하면 되기 때문에 생각보다 계산량이 많지 않다
-
queue를 하나씩 빼면서 내가 움직일 방향의 행,열의 0번 or n-1번 인덱스부터 넣으면서 조건 판별 ex) 2,2,2가 queue에 있을 때 앞에 2,2는 합쳐서 4로 만들어주고 2는 합치지 않아야 한다
-
고민했던 부분
- 재귀를 돌리다가 어떤 값이 제대로 초기화가 안 되거나 값이 이상하게 나온다면 항상 static변수로 선언된 배열이나 값에 문제가 있다
- 일단 메모리 생각하지 말고 계속해서 초기화 해야하는 값이라면 for문 돌리면서 초기화 하는 거 보다는 그냥 객체를 초기화 하는게 더 이득
- 상하좌우로 하면서 이전 값과 움직인 후의 값 비교해서 똑같은 값 재귀로 다시 안 보내는 로직으로 구현했는데 딱히 시간적 효율이 없다?
