백준 12100번 - 2048(easy)

구현 방법

문제: 5번을 이동을 했을 때 마주할 수 있는 가장 큰 값은?

 

이동 횟수를 보거나 풀이 과정을 생각해 보았을 때 귀납적 추론에 의한 문제는 아니다. 절차지향적 방식으로 순차적으로 접근하는 것이다.

재귀를 이용한 백트래킹 vs 반복문을 통한 백트래킹 둘다 가능할 것 같다.  (저는 이제 반복문이 가능하다면 이 방식을 선호하긴 한다.)

재귀를 이용한 백트래킹 방식은 케이스 하나에 대해서 가지를 뻗는 방식이라면 반복문을 통한 백트래킹은 전체 상태를 정해놓고 처리하는 방식이다. 반복문을 통한 백트래킹 시 진법을 이용한 방식(2진법, 4진법 이면 표현하기 쉽다)으로 쉽게 접근할 수 있다.

 

이 문제에서 중요했던 포인트는 이동 방향이 정해졌을 때 이동을 어떻게 처리할까 인 것 같다.

내가 처음에 접근한 방식은 다음과 같다.( <- 방향)

for(int i = 0; i < copyMap.length; i++){
    boolean[] isMerged = new boolean[N];
    for(int j = 0; j < copyMap[0].length; j++){
        for(int k = j; k > 0; k--){
            if(copyMap[i][k - 1] == 0){
                copyMap[i][k - 1] = copyMap[i][k];
                copyMap[i][k] = 0;
                continue;
            }
            else if(!isMerged[k - 1] &&copyMap[i][k - 1] == copyMap[i][k]){
                copyMap[i][k - 1] = copyMap[i][k] * 2;
                copyMap[i][k] = 0;
                isMerged[k - 1] = true;
            }
            break;
        }
    }
}

 

삼중 반복문으로 처리해서 시간이 오래 걸리는 풀이이다.

다시 생각해봤을 때 가장 안쪽의 반복문이 굳이 필요할까라고 생각이 들었다. 이동 방향으로 한칸씩 이동을 할 필요가 없이 이동 방향에 끝부터 채우는 식으로 접근을 하면 반복문 한 겹을 없앨 수 있다.

코드

package simulation;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ12100{
    private static int N;
    private static int[][] map, copyMap;
    private static int result = 0;
    public static void main(String[] args)throws IOException {
        readInput();
        solve();
    }

    private static void readInput() 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());
            }
        }
    }

    private static void solve(){
        for(int status = 0; status < (1 << 10); status++){
            int temp = status;

            copyMap = new int[map.length][map[0].length];

            for(int i = 0; i < map.length; i++){
                for(int j = 0; j < map[0].length; j++){
                    copyMap[i][j] = map[i][j];
                }
            }

            for(int i = 0; i < 5; i++){
                int dir = temp % 4;
                temp /= 4;
                move(dir);
            }
            getMaxResult();
        }

        System.out.println(result);
    }

    private static int getMaxResult(){
        int value = 0;
        for(int i = 0 ; i < copyMap.length; i++){
            for(int j = 0; j < copyMap[0].length; j++){
                value = Math.max(value, copyMap[i][j]);
            }
        }
        result = Math.max(result, value);
        return value;
    }

    private static void move(int dir){
        if(dir == 0){
            for(int i = 0; i < N; i++){
                int[] tempArr = new int[N];
                int idx = 0;
                for(int j = N - 1; j >= 0; j--){
                    if(copyMap[j][i] == 0) continue;
                    else if(tempArr[idx] == copyMap[j][i]) tempArr[idx++] = copyMap[j][i] * 2;
                    else if(tempArr[idx] == 0) tempArr[idx] = copyMap[j][i];
                    else tempArr[++idx] = copyMap[j][i];

                }

                for(int j = N - 1; j >= 0; j--){
                    copyMap[j][i] = tempArr[N - 1 -j];
                }
            }
        }
        else if(dir == 1){
            for(int i = 0; i < N; i++){
                int[] tempArr = new int[N];
                int idx = 0;
                for(int j = N - 1; j >= 0; j--){
                    if(copyMap[i][j] == 0) continue;
                    else if(tempArr[idx] == copyMap[i][j]) tempArr[idx++] = copyMap[i][j] * 2;
                    else if(tempArr[idx] == 0) tempArr[idx] = copyMap[i][j];
                    else tempArr[++idx] = copyMap[i][j];
                }

                for(int j = N - 1; j >= 0; j--){
                    copyMap[i][j] = tempArr[N - 1 -j];
                }
            }
        }
        else if(dir == 2){
            for(int i = 0; i < N; i++){
                int[] tempArr = new int[N];
                int idx = 0;
                for(int j = 0; j < N; j++){
                    if(copyMap[j][i] == 0) continue;
                    else if(tempArr[idx] == copyMap[j][i]) tempArr[idx++] = copyMap[j][i] * 2;
                    else if(tempArr[idx] == 0) tempArr[idx] = copyMap[j][i];
                    else tempArr[++idx] = copyMap[j][i];
                }

                for(int j = 0; j < N; j++){
                    copyMap[j][i] = tempArr[j];
                }
            }
        }
        else if(dir == 3){
            for(int i = 0; i < N; i++){
                int[] tempArr = new int[N];
                int idx = 0;
                for(int j = 0; j < N; j++){
                    if(copyMap[i][j] == 0) continue;
                    else if(tempArr[idx] == copyMap[i][j]) tempArr[idx++] = copyMap[i][j] * 2;
                    else if(tempArr[idx] == 0) tempArr[idx] = copyMap[i][j];
                    else tempArr[++idx] = copyMap[i][j];
                }

                for(int j = 0; j < N; j++){
                    copyMap[i][j] = tempArr[j];
                }
            }
        }
    }
}

다른 사람 풀이를 참고했을 때 move 함수에서 이동 방향에 따라 분기를 처리하는 것이 아니라 게임 보드를 회전을 하고 move 함수는 단일 경우에 대해서는 정의하니 코드가 깔끔해지는 것을 볼 수 있었다.

결과