백준 12100 2048 (easy) java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/12100

(1) 조건 분석 📊

1. 한 번의 이동에서 합쳐진 수는 또 다른 블록과 합쳐질 수 없다.

2. 총 5번까지만 기울인다.

2. 코드가 나오기까지 🛠️

1. 동서남북으로 기울여서 합치는 함수

2. dfs 재귀 함수

(1) 시간복잡도 분석 ⏳

1. 각 깊이마다 노드별로 자식 노드가 4개씩 더 생긴다.

2. 하나의 노드 당 2차원 배열을 한 번 순회한다.

3. 코드 🌐

(1) SUDO CODE 💬

// 풀이 설명이 다라서 생략

(2) JAVA CODE ☕

import java.util.*;
import java.io.*;
 // b 17255 N으로 만들기
public class Main {
    static int N;
    static int [][] map;
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                answer = Math.max(answer, map[i][j]);
            }        }

        back_tracking(map, 0);
        System.out.println(answer);
     }
     public static void back_tracking(int [][] prev, int depth){
        if(depth >= 5) return;

        int [][] east = new int [N][N];
        answer = Math.max(answer, tilt(prev, east, 0));
        back_tracking(east, depth+1);

        int [][] west = new int [N][N];
        answer = Math.max(answer, tilt(prev,west,1));
        back_tracking(west, depth+1);


        int [][] south = new int [N][N];
        answer = Math.max(answer, tilt(prev,south,2));
        back_tracking(south, depth+1);

        int [][] north = new int [N][N];
        answer = Math.max(answer,tilt(prev, north, 3));
        back_tracking(north, depth+1);

//         System.out.printf("depth: %d", depth);
//         print(0,east);
//         print(1, west);
//         print(2, south);
//         print(3, north);
     }
     public static int tilt (int [][] prev, int [][] ans, int dir) {
        int max = 0;
        switch (dir){
            case 0 : {
                for(int r = 0 ; r < N; r++){
                    int p1, p2;
                    p1 = p2 = N-1;

                    while (p1 >= 0){
                        if(prev[r][p1] == 0){
                            p1--;
                            continue;
                        }                        if(ans[r][p2] == 0) ans[r][p2] = prev[r][p1];
                        else if(prev[r][p1] == ans[r][p2]) {
                            ans[r][p2]*=2;
                            max = Math.max(max, ans[r][p2--]);
                        }                        else ans[r][--p2] = prev[r][p1];
                        p1--;
                    }                }                break;
            }            case 1: {
                for(int i = 0; i < N; i++){
                    int p1,p2;
                    p1 = p2 = 0;
                    while (p1 < N){
                        if(prev[i][p1] == 0) {
                            p1++;
                            continue;
                        }                        if(ans[i][p2] == 0) ans[i][p2] = prev[i][p1];
                        else if (ans[i][p2] == prev[i][p1]) {
                            ans[i][p2] *=2;
                            max = Math.max(max,ans[i][p2++]);
                        }                        else ans[i][++p2] = prev[i][p1];
                        p1++;
                    }                }                break;
            }            case 2: {
                for(int i = 0; i < N; i++){
                    int p1,p2;
                    p1 = p2 = N-1;

                    while (p1 >= 0){
                        if(prev[p1][i] == 0) {
                            p1--;
                            continue;
                        }                        if(ans[p2][i] == 0) ans[p2][i] = prev[p1][i];
                        else if (ans[p2][i] == prev[p1][i]) {
                            ans[p2][i] *=2;
                            max = Math.max(ans[p2--][i], max);

                        }                        else ans[--p2][i] = prev[p1][i];
                        p1--;
                    }                }                break;
            }            case 3: {
                for(int i = 0; i < N; i++){
                    int p1,p2;
                    p1 = p2 = 0;

                    while (p1 < N){
                        if(prev[p1][i] == 0) {
                            p1++;
                            continue;
                        }                        if(ans[p2][i] == 0) ans[p2][i] = prev[p1][i];
                        else if (ans[p2][i] == prev[p1][i]) {
                            ans[p2][i] *=2;
                            max = Math.max(ans[p2++][i], max);
                        }                        else ans[++p2][i] = prev[p1][i];
                        p1++;
                    }                }                break;
            }        }        return max;
     }
     public static void print (int dir, int [][] temp){
         switch (dir){
             case 0:
                 System.out.println("동");
                 break;
             case 1:
                 System.out.println("서");
                 break;
             case 2:
                 System.out.println("남");
                 break;
             case 3:
                 System.out.println("북");
                 break;
         }         for(int [] row : temp){
             System.out.println(Arrays.toString(row));
         }         System.out.println();
     }
 }

4. 트러블 슈팅 or 배운 점📝

• 기울이기 함수를 switch 없이 인수와 간단한 공식으로 만들려 했는데, 각각 시작 위치와 행,열이 달라서 실패했다. 이거 한 사람 나중에 찾아서 참고해봐야겠다.

• 실수했던 파트는 한 번도 병합이 일어나지 않는 경우를 체크하지 않았고, 깊이를 5번까지 세야 하는데 6번까지 셌었던 파트이다.