백준 12100 번 : 2048 (Easy) 풀이 ( 삼성 SW 역량 테스트 기출 문제 )

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

곧 SSAFY 에서 있을 삼성 SW 역량 테스트 A형 모의고사를 대비해 기출문제를 풀어보았다.

A형 취득할 수 있을지 걱정된다...

Solution

1. A형 문제는 대체로 완전탐색을 돌려도 문제가 없다고 하길래, 내 수준을 감안해서 완전탐색 말고는 생각을 하지 않기로 했다.

2. 먼저 방향에 따라서 배열을 움직이는 shift() 메서드를 만들었다. 방향이 상하좌우로 4가지, 최대 5번을 돌리므로, 4^5 만큼의 shift() 가 수행되어야 한다.

3. shift 의 파라미터에 depth 를 넣어서, 5번이 될 경우 return 시켜서 끝내버린다. 이후 map 을 이동시키고 나서, 상하좌우 4방향으로 shift 재귀를 돌려준다. 이 때, 상하좌우 shift의 파라미터로 들어가는 map의 메모리 주소가 같으면 안되므로 deepcopy 를 수행해야 한다.

4. 이게 무슨 말이냐면, 만약 0번째 수행에서 1번째 수행으로 가기 위해 반복문을 돌리면

shift(map, dir, depth+1);
shift(map, dir, depth+1);
shift(map, dir, depth+1);
shift(map, dir, depth+1);

이렇게 풀어질텐데, 이는 map이 같은 주소를 가진 채로 재귀가 수행되므로 상->하->좌->우 가 이전의 결과값을 바탕으로 실행이 된다. 그렇기에, 각 함수마다

 

shift(cloneMap(map), dir, depth+1);
shift(cloneMap(map), dir, depth+1);
shift(cloneMap(map), dir, depth+1);
shift(cloneMap(map), dir, depth+1);

이런 식으로 deepcopy 를 해주는 cloneMap 함수를 이용해서 각각의 결과가 독립적이도록 했다.

5. 이제 shift 함수를 구현해보면,

- 0번 : 위로 이동

맨 위에서 바로 아래부터(1번 열부터), (map[x][y])

바로 위의 열을 봤을 때, (map[x-1][y])

0이라면 -> 0이 아닐 때 까지 swap 을 해주면서 이동한다.

0이 아니라면?

-> 만약 같은 값이라면, map[x-1][y] 에 곱하기 2를 해주고, map[x][y] = 0 으로 만들어준다.

    - !중요! 연쇄 반응이 없다고 문제에 나와 있으므로, 한 번 이렇게 합쳐진 곳은 다시 합쳐지지 않도록, summed 라는 boolean 2차원 배열에 기록해둔다.

-> 다른 값이라면 그냥 break

 

6. 한 번 이동해주고, 2차원 배열을 돌면서 max 값을 저장한다.

7. 이후 위에서 말한 것 처럼 4방향으로 shift 를 돌려주면 된다.

 

Source Code

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

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, max;
    static int[][] map;

    static void input() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        map = new int[N][N];
        for(int i = 0 ; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    static boolean isOut(int nx, int ny) {
        return nx < 0 || ny < 0 || nx >= N || ny >= N;
    }

    static int[][] swap(int[][] map, int x, int y, int nx, int ny) {
        int temp = map[x][y];
        map[x][y] = map[nx][ny];
        map[nx][ny] = temp;
        return map;
    }

    static void findMax(int[][] map) {
        for(int i = 0 ; i < N; i++) {
            for(int j = 0; j < N; j++) {
                max = Math.max(max, map[i][j]);
            }
        }
    }

    static int[][] shift(int[][] map, int dir, boolean[][] summed, int depth) {
        if(depth == 5) {
            return null;
        }
        //System.out.println(depth + "회차 : " + "방향 : " + dir);
        switch (dir) {
            case 0:
                for(int x = 1; x < N; x++) {
                    for(int y = 0; y < N; y++) {
                        int nx = x;
                        while (!isOut(nx-1, y) && map[nx-1][y] == 0) {
                            map = swap(map, nx, y, nx-1, y);
                            nx--;
                        }
                        int nnx = nx;
                        while (!isOut(nnx-1, y)) {
                            if(map[nnx][y] == map[nnx-1][y] && !summed[nnx-1][y] && !summed[nnx][y]) {
                                map[nnx-1][y] *= 2;
                                map[nnx][y] = 0;
                                summed[nnx-1][y] = true;
                            } else {
                                break;
                            }
                            nnx--;
                        }
                    }
                }
                break;
            case 1:
                for(int x = 0; x < N; x++) {
                    for(int y = N-2; y >= 0; y--) {
                        int ny = y;
                        while (!isOut(x, ny+1) && map[x][ny+1] == 0) {
                            map = swap(map, x, ny, x, ny+1);
                            ny++;
                        }
                        int nny = ny;
                        while (!isOut(x, nny+1)) {
                            if(map[x][nny] == map[x][nny+1] && !summed[x][nny+1] && !summed[x][nny]) {
                                map[x][nny+1] *= 2;
                                map[x][nny] = 0;
                                summed[x][nny+1] = true;
                            } else {
                                break;
                            }
                            nny++;
                        }
                    }
                }
                break;
            case 2:
                for(int x = N-2; x >= 0; x--) {
                    for(int y = 0; y < N; y++) {
                        int nx = x;
                        while (!isOut(nx+1, y) && map[nx+1][y] == 0) {
                            map = swap(map, nx, y, nx+1, y);
                            nx++;
                        }
                        int nnx = nx;
                        while (!isOut(nnx+1, y)) {
                            if(map[nnx][y] == map[nnx+1][y] && !summed[nnx+1][y] && !summed[nnx][y]) {
                                map[nnx+1][y] *= 2;
                                map[nnx][y] = 0;
                                summed[nnx+1][y] = true;
                            } else {
                                break;
                            }
                            nnx++;
                        }
                    }
                }
                break;
            case 3:
                for(int x = 0; x < N; x++) {
                    for(int y = 1; y < N; y++) {
                        int ny = y;
                        while (!isOut(x, ny-1) && map[x][ny-1] == 0) {
                            map = swap(map, x, ny, x, ny-1);
                            ny--;
                        }
                        int nny = ny;
                        while (!isOut(x, nny-1)) {
                            if(map[x][nny] == map[x][nny-1] && !summed[x][nny-1] && !summed[x][nny]) {
                                map[x][nny-1] *= 2;
                                map[x][nny] = 0;
                                summed[x][nny-1] = true;
                            } else {
                                break;
                            }
                            nny--;
                        }
                    }
                }
                break;
        }
        findMax(map);
        for(int i = 0 ; i < 4; i++) {
            shift(cloneMap(map), i, new boolean[N][N], depth+1);
        }
        return map;
    }

    static int[][] cloneMap(int[][] map) {
        int[][] clone = new int[N][N];
        for(int i = 0; i < N; i++) {
            clone[i] = map[i].clone();
        }
        return clone;
    }

    static void solve() {
        for(int j = 0; j < 4; j++) {
            shift(cloneMap(map), j, new boolean[N][N], 0);
        }
        System.out.println(max);
    }


    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}