b12100. 2048(Easy)

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

 

 

 

이 2048 문제는 보드를 최대 5번 이동한 후 가장 큰 블록 값을 계산하는 문제다.

기존 코드에서는 DFS를 통해 모든 이동 조합을 생성한 뒤,
완성된 조합에 대해 5번의 방향 이동을 한꺼번에 처리했다.
이 방식은 각 단계에서 이동 상태를 효율적으로 관리하지 못하고,
불필요한 회전 및 복구 연산이 반복되는 문제점이 있었다.
이를 해결하기 위해 saved와 board 변수를 활용하여 현재 상태를 효과적으로 관리하며,
이동 조작을 단계적으로 수행하는 방식으로 개선했다.

board는 입력받은 초기 보드 상태를 저장하는 변수로, 탐색 과정에서 변경되지 않는 원본 데이터를 담고 있다. 반면, saved는 현재 DFS 탐색 중의 보드 상태를 관리하는 변수다.
saved는 각 DFS 단계에서 변경되며,

재귀 호출 전후로 깊은 복사를 통해 상태를 저장하고 복구한다.

이를 통해 상태 관리가 명확해지고, 매번 원본 데이터를 다시 초기화할 필요가 없어졌다.

방향 이동은 applyDirection 메서드를 통해 처리한다. 이 메서드는 이동 방향에 따라 블록들을 밀고 합치는 작업을 수행하며, 이를 위해 merge, rotate, flip 등의 보조 메서드가 활용된다.
merge는 기본적으로 블록을 왼쪽으로 이동시키고 합치는 작업을 처리하며,
다른 방향의 이동은 rotate와 flip을 조합해 구현했다.

예를 들어, 오른쪽 이동은 먼저 보드를 180도 회전한 후 왼쪽으로 합치고,
다시 원래 상태로 복구하는 방식으로 처리한다.
위쪽과 아래쪽 이동은 전치와 회전을 조합해 간결하게 구현했다.

DFS 탐색은 combination 메서드를 통해 이루어진다.
각 단계에서는 현재 방향으로 이동을 수행하고,
다음 단계로 재귀 호출을 진행한다.
호출이 끝난 후에는 상태를 복구하여 다른 방향으로의 이동을 시도할 수 있도록 했다.
이를 통해 각 단계에서 한 번의 이동만 수행하고,
중복 연산 없이 다음 단계로 넘어가는 구조를 구현했다.

조합이 완성되었을 때, 즉 DFS의 깊이가 5가 되었을 때는 현재 saved 상태에서 최대 블록 값을 계산하여 answer에 반영한다.

아래의 첫번째 코드는 개선 후 코드 다음 코드는 개선 전 코드이다.

 

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int N, answer = 0;
    static int[][] board, saved;

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static void merge() {
        for (int i = 0; i < N; i++) {
            int[] arr = new int[N];
            int idx = 0;
            for (int n : saved[i]) {
                if (n != 0) arr[idx++] = n;
            }
            for (int j = 0; j < N - 1; j++) {
                if (arr[j] == arr[j + 1]) {
                    arr[j] *= 2;
                    arr[j + 1] = 0;
                    j++;
                }
            }
            int[] ans = new int[N];
            idx = 0;
            for (int n : arr) {
                if (n != 0) ans[idx++] = n;
            }
            saved[i] = ans;
        }
    }

    static void rotate() {
        int[][] rotated = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                rotated[N - j - 1][i] = saved[i][j];
        saved = rotated;
    }

    static void flip() {
        int[][] fliped = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                fliped[N - i - 1][N - j - 1] = saved[i][j];
        saved = fliped;
    }

    static void applyDirection(int dir) {
        if (dir == 1) {
            merge();
        } else if (dir == 2) {
            flip();
            merge();
            flip();
        } else if (dir == 3) {
            rotate();
            merge();
        } else if (dir == 4) {
            flip();
            rotate();
            merge();
            rotate();
        }
    }

    static void combination(int depth) {
        if (depth == 5) {
            for (int i = 0; i < N; i++)
                for (int m : saved[i])
                    answer = Math.max(answer, m);
            return;
        }
        int[][] original = new int[N][N];
        for (int i = 0; i < N; i++) {
            original[i] = saved[i].clone();
        }
        for (int dir = 1; dir <= 4; dir++) {
            applyDirection(dir);
            combination(depth + 1);
            saved = original;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = stoi(br.readLine());
        board = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = stoi(st.nextToken());
            }
        }
        saved = new int[N][N];
        for (int i = 0; i < N; i++) {
            saved[i] = board[i].clone();
        }
        combination(0);
        System.out.println(answer);
    }
}

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int N, answer = 0;
    static int[][] board, saved;

    static int stoi(String s) {
        return Integer.parseInt(s);
    }
    
    static void merge() {
        for (int i = 0; i < N; i++) {
            int[] arr = new int[N];
            int idx = 0;
            for (int n : saved[i]) {
                if (n != 0) arr[idx++] = n;
            }

            for (int j = 0; j < N - 1; j++) {
                if (arr[j] == arr[j + 1]) {
                    arr[j] *= 2;
                    arr[j + 1] = 0;
                    j ++;
                }
            }
            int[] ans = new int[N];
            idx = 0;
            for (int n : arr) {
                if (n != 0) ans[idx++] = n;
            }
            saved[i] = ans;
        }
    }

    static void rotate() {
        int[][] rotated = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                rotated[N - j - 1][i] = saved[i][j];
        saved = rotated;
    }

    static void flip() {
        int[][] fliped = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                fliped[N - i - 1][N - j - 1] = saved[i][j];
        saved = fliped;
    }

    static void allMerge(int[] arr) {
        saved = new int[N][N];
        for (int i = 0; i < N; i++) 
            saved[i] = board[i].clone();
        

        for (int i = 0; i < 5; i++) {
            if (arr[i] == 2) rotate();
            else if (arr[i] == 3) {
                rotate();
                rotate();
            }
            else if (arr[i] == 4) {
                rotate();
                rotate();
                rotate();
            }
            merge();
            if (arr[i] == 2) {
                rotate();
                rotate();
                rotate();
            } else if (arr[i] == 3){
                rotate();rotate();
            }
            else if (arr[i] == 4) rotate();
        }
        for (int i = 0; i < N; i++) {
            for (int m : saved[i]) {
                answer = Math.max(answer, m);
            }
        }
    }

    static void combination(int depth, int[] arr) {
        if (depth == 5) {
            allMerge(arr);
            return;
        }
        for (int i = 1; i <= 4; i++) {
            arr[depth] = i;
            combination(depth + 1, arr);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = stoi(br.readLine());
        board = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = stoi(st.nextToken());
            }
        }
        combination(0, new int[5]);
        System.out.println(answer);
    }
}

 

시간복잡도 57%, 메모리사용량 67% 성능개선