BAEK12100. 2048(Easy)

2023년 5월 9일

https://www.acmicpc.net/problem/12100

시간 : ❤❤❤❤❤

만족도 : ❤❤❤❤❤

• 백트래킹 알고리즘 사용
• 각각의 횟수에서 상, 하, 좌, 우로 움직이는 모든 경우를 탐색한다.
• 계속 이중 배열의 값이 바뀌기 때문에 상, 하, 좌, 우 메소드 안에서 깊은 복사를 해주었다.

• 코드

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Deque;
    import java.util.LinkedList;
    import java.util.StringTokenizer;
  
    public class Main {
        static int N;
        static int[][] graph;
        static int max = Integer.MIN_VALUE;
        static Deque<Integer> q = new LinkedList<>();
        public static void main(String[] args) throws NumberFormatException, IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st;
            N = Integer.parseInt(br.readLine());
            graph = new int[N][N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    graph[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            dfs(0, graph);
            System.out.println(max);
        }
  
        public static void dfs(int cnt, int[][] map) {
            // base case
            if (cnt == 5) {
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        max = Math.max(max, map[i][j]);
                    }
                }
                return;
            }
            // recur case
            dfs(cnt + 1, left(map));
            dfs(cnt + 1, right(map));
            dfs(cnt + 1, up(map));
            dfs(cnt + 1, down(map));
        }
  
        // 왼쪽방향일 때
        public static int[][] left(int[][] map) {
            // 깊은 복사 진행
            int[][] temp = new int[N][N];
  
            for (int i = 0; i < N; i++) temp[i] = map[i].clone();
  
            for (int i = 0; i < N; i++) {
                // 2개가 합쳐졌을 때 연속으로 합쳐지지 않기 위한 boolean 변수 선언
                boolean flag = false;
                for (int j = 0; j < N; j++) {
                    if (temp[i][j] != 0) {
                        // 큐가 비어있지 않거나, q에서 가장 마지막 값이 현재값과 같을 때
                        if (!q.isEmpty() && q.peekLast() == temp[i][j] && !flag) {
                            // 둘을 합친다..
                            q.addLast(q.pollLast() * 2);
                            flag = true;
                        // 큐가 비어있을 때 채워준다.
                        } else {
                            q.add(temp[i][j]);
                            flag = false;
                        }
                        // 현재 행을 전부 0으로 바꾼다.
                        temp[i][j] = 0;
                    }
                }
                int idx = 0;
                // 비워진 현재 행을 큐에 담긴 값으로 순서대로 채워준다.
                while(!q.isEmpty()) {
                    temp[i][idx++] = q.pollFirst();
                }
            }
            return temp;
        }
  
        public static int[][] right(int[][] map) {
            int[][] temp = new int[N][N];
  
            for (int i = 0; i < N; i++) temp[i] = map[i].clone();
  
            for (int i = 0; i < N; i++) {
                boolean flag = false;
                for (int j = N-1; j >= 0; j--) {
                    if (temp[i][j] != 0) {
                        if (!q.isEmpty() && q.peekLast() == temp[i][j] && !flag) {
                            q.addLast(q.pollLast() * 2);
                            flag = true;
                        } else {
                            q.add(temp[i][j]);
                            flag = false;
                        }
                        temp[i][j] = 0;
                    }
                }
                int idx = N-1;
                while(!q.isEmpty()) {
                    temp[i][idx--] = q.pollFirst();
                }
            }
            return temp;
        }
  
        public static int[][] up(int[][] map) {
            int[][] temp = new int[N][N];
  
            for (int i = 0; i < N; i++) temp[i] = map[i].clone();
  
            for (int j = 0; j < N; j++) {
                boolean flag = false;
                for (int i = 0; i < N; i++) {
                    if (temp[i][j] != 0) {
                        if (!q.isEmpty() && q.peekLast() == temp[i][j] && !flag) {
                            q.addLast(q.pollLast() * 2);
                            flag = true;
                        } else {
                            q.add(temp[i][j]);
                            flag = false;
                        }
                        temp[i][j] = 0;
                    }
                }
                int idx = 0;
                while(!q.isEmpty()) {
                    temp[idx++][j] = q.pollFirst();
                }
            }
            return temp;
        }
  
        public static int[][] down(int[][] map) {
            int[][] temp = new int[N][N];
  
            for (int i = 0; i < N; i++) temp[i] = map[i].clone();
  
            for (int j = 0; j < N; j++) {
                boolean flag = false;
                for (int i = N - 1; i >= 0; i--) {
                    if (temp[i][j] != 0) {
                        if (!q.isEmpty() && q.peekLast() == temp[i][j] && !flag) {
                            q.addLast(q.pollLast() * 2);
                            flag = true;
                        } else {
                            q.add(temp[i][j]);
                            flag = false;
                        }
                        temp[i][j] = 0;
                    }
                }
                int idx = N - 1;
                while(!q.isEmpty()) {
                    temp[idx--][j] = q.pollFirst();
                }
            }
            return temp;
        }
    }