백준 12100 (2048 (Easy))

문제

12100번: 2048 (Easy)

N * N의 크기의 2차원 배열이 주어진다.

대충 맨 왼쪽 그림처럼 주어지면 여기서 위로 이동시킨것이 2번째 그림이다.

3번째 그림에서 위로 움직인것이 4번째 그림이다.

 

이렇게 동서남북 아무 방향이나 총 5번 움직일 수 있다.

여기서 만들어지는 가장 큰 수를 구하는 문제이다.

---

이 문제는 재귀함수를 사용해 브루트포스, 백 트래킹으로 문제를 해결할 수 있었다.

중요한 점은 2차원 배열이 계속 움직이면서 어떻게 저장하고, 임시 배열에 복사를 할것인지가 관건이었다.

먼저 기본틀을 보자.

private static void sol(int count){
        if(count == 5){
            //제일 최고 칸 구해서 갱신
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    BIG = Math.max(BIG, map[i][j]);
                }
            }
            return;
        }

        int[][] temp = new int[n][n];
        for(int i=0;i<n;i++){
            temp[i] = map[i].clone(); //임시 배열 복사
        }

        east();
        sol(count+1);
        for(int i=0;i<n;i++){
            map[i] = temp[i].clone(); //임시 배열 복사
        }
        
        west();
        sol(count+1);
        for(int i=0;i<n;i++){
            map[i] = temp[i].clone(); //임시 배열 복사
        }
        
        south();
        sol(count+1);
        for(int i=0;i<n;i++){
            map[i] = temp[i].clone(); //임시 배열 복사
        }
        
        north();
        sol(count+1);
        for(int i=0;i<n;i++){
            map[i] = temp[i].clone(); //임시 배열 복사
        }
    }

count가 5가되면 최대로 이동한 것이기 때문에 모든 배열을 순회 하면서 최댓값을 찾아준다.

temp라는 임시 배열을 선언해준다.

현재 상태를 기억해 두기 위함이다.

우리는 east, west, south, north 4방향을 모두 초기화된 상태에서 들어가야한다.

따라서 temp 임시 배열에 이동하지 않은 현재 상태를 기억해 두는 것이다.

이제 예를 들어 east를 했다고 하면 map의 배열 상태는 east로 움직인 상태이다.

그 상태에서 sol() 함수를 재귀 호출해준다.

다시 return 되어서 돌아올 때는 이동되지 않은 깨끗한 temp를 다시 map으로 복사해주는것이다.

 

private static void east() {
        boolean [][]check = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            int location = -1;
            for (int j = n - 1; j >= 0; j--) {
                if (map[i][j] == 0)
                    continue; //빈공간일 경우

                if (location == -1) { //맨 처음에 빈공간이 아닌 경우 그대로 이동
                    if(j != n-1) {
                        map[i][n - 1] = map[i][j];
                        map[i][j]=0;
                    }
                    location = n-1;
                } else if (map[i][j] == map[i][location] && !check[i][location]) {
                    map[i][location] = map[i][location] * 2;
                    map[i][j] = 0;
                    check[i][location] = true;
                } else if (map[i][j] == map[i][location] && check[i][location]) {
                    map[i][location - 1] = map[i][j];
                    map[i][j] = 0;
                    location--;
                } else if (map[i][j] != map[i][location]) {
                    map[i][location - 1] = map[i][j];
                    if(j != location -1)map[i][j]=0;
                    location--;
                }
            }
        }
    }

이동하는 함수는 크게 4가지가 존재한다.

이동하는 방향 순서대로 탐색한다.

1. 맨 처음에 0이 아닌 블록이 생기면 그대로 블록 맨 끝으로 이동시킨다.

여기서 location 변수를 활용해 현재 블록이 있는 위치를 저장한다. 처음 location은 -1이다.

2. 현재 블록과 location에 있는 블록의 크기가 같고 check[location]이 false이면 블록을 합친다.

3. 현재 블록과 location에 있는 블록의 크기가 같고 check[location]이 true이면 블록을 합치지 않고 location 앞에 위치시킨다.

4. 현재 블록과 location에 있는 블록 크기가 다르면 현재 블록을 location앞에 위치시킨다.

---

전체 코드이다.

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

public class Main {
    private static int n;
    private static int[][] map;
    private static boolean[][]isUnion;
    private static int BIG=-1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        map = new int[n][n];
        isUnion = new boolean[n][n];

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

        sol(0);
        System.out.println(BIG);

    }
    private static void sol(int count){
        if(count == 5){
            //제일 최고 칸 구해서 갱신
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    BIG = Math.max(BIG, map[i][j]);
                }
            }
            return;
        }

        int[][] temp = new int[n][n];
        for(int i=0;i<n;i++){
            temp[i] = map[i].clone(); //임시 배열 복사
        }


        east();
        sol(count+1);
        for(int i=0;i<n;i++){
            map[i] = temp[i].clone(); //임시 배열 복사
        }
        
        west();
        sol(count+1);
        for(int i=0;i<n;i++){
            map[i] = temp[i].clone(); //임시 배열 복사
        }
        
        south();
        sol(count+1);
        for(int i=0;i<n;i++){
            map[i] = temp[i].clone(); //임시 배열 복사
        }
        
        north();
        sol(count+1);
        for(int i=0;i<n;i++){
            map[i] = temp[i].clone(); //임시 배열 복사
        }
    }
    private static void east() {
        boolean [][]check = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            int location = -1;
            for (int j = n - 1; j >= 0; j--) {
                if (map[i][j] == 0)
                    continue; //빈공간일 경우

                if (location == -1) { //맨 처음에 빈공간이 아닌 경우 그대로 이동
                    if(j != n-1) {
                        map[i][n - 1] = map[i][j];
                        map[i][j]=0;
                    }
                    location = n-1;
                } else if (map[i][j] == map[i][location] && !check[i][location]) {
                    map[i][location] = map[i][location] * 2;
                    map[i][j] = 0;
                    check[i][location] = true;
                } else if (map[i][j] == map[i][location] && check[i][location]) {
                    map[i][location - 1] = map[i][j];
                    map[i][j] = 0;
                    location--;
                } else if (map[i][j] != map[i][location]) {
                    map[i][location - 1] = map[i][j];
                    if(j != location -1)map[i][j]=0;
                    location--;
                }
            }
        }
    }
    private static void west(){
        boolean [][]check = new boolean[n][n];
        for(int i=0;i<n;i++){
            int location = -1;
            for(int j=0;j<n;j++){
                if(map[i][j] ==0)continue;

                if(location == -1){
                    if(j != 0) {
                        map[i][0] = map[i][j];
                        map[i][j]=0;
                    }
                    location = 0;
                }
                else if(map[i][j] == map[i][location] && !check[i][location]){
                    map[i][location] = map[i][location] * 2;
                    map[i][j] = 0;
                    check[i][location] = true;
                } else if (map[i][j] == map[i][location] && check[i][location]) {
                    map[i][location + 1] = map[i][j];
                    map[i][j] = 0;
                    location++;
                } else if (map[i][j] != map[i][location]) {
                    map[i][location + 1] = map[i][j];
                    if(j !=location +1)map[i][j]=0;
                    location++;
                }
            }
        }
    }

    private static void south(){
        boolean [][]check = new boolean[n][n];
        for(int i=0;i<n;i++){
            int location = -1;
            for(int j=n-1;j>=0;j--){
                if(map[j][i] ==0)continue;

                if(location == -1){
                    if(j != n-1) {
                        map[n-1][i] = map[j][i];
                        map[j][i]=0;
                    }
                    location = n-1;
                }
                else if(map[j][i] == map[location][i] && !check[location][i]){
                    map[location][i] = map[location][i] * 2;
                    map[j][i] = 0;
                    check[location][i] = true;
                } else if (map[j][i] == map[location][i] && check[location][i]) {
                    map[location-1][i] = map[j][i];
                    map[j][i] = 0;
                    location--;
                } else if (map[j][i] != map[location][i]) {
                    map[location-1][i] = map[j][i];
                    if(j != location -1)map[j][i]=0;
                    location--;
                }
            }
        }
    }
    private static void north(){
        boolean [][]check = new boolean[n][n];
        for(int i=0;i<n;i++){
            int location = -1;
            for(int j=0;j<n;j++){
                if(map[j][i] ==0)continue;

                if(location == -1){
                    if(j != 0) {
                        map[0][i] = map[j][i];
                        map[j][i]=0;
                    }
                    location = 0;
                }
                else if(map[j][i] == map[location][i] && !check[location][i]){
                    map[location][i] = map[location][i] * 2;
                    map[j][i] = 0;
                    check[location][i] = true;
                } else if (map[j][i] == map[location][i] && check[location][i]) {
                    map[location+1][i] = map[j][i];
                    map[j][i] = 0;
                    location++;
                } else if (map[j][i] != map[location][i]) {
                    map[location+1][i] = map[j][i];
                    if(j != location +1)map[j][i]=0;
                    location++;
                }
            }
        }
    }
}