난이도

Gold 2

풀이 참고 유무

x

막힌 부분

구현이 어려움

문제

문제 바로가기

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

예제 입력

3
2 2 2
4 4 4
8 8 8

예제 출력

16

문제 검토

최대 5번이라고 했으니 depth가 5인 백트랙킹으로 완전탐색을 하면 될 것 같다.
구현이 어려워 보인다.

풀이

Java

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

//아이디어:
// 상하좌우 4번 반복하는 depth가 5인 백트랙킹을 진행
// 1. 방향 가장 가까운 블록을 방향으로 이동
//-> -> : 0이 아니면 멈추고 숫자를 확인
// -> 조건1: 숫자가 다르면 그 앞에서 멈춰야함
// -> 조건2: 숫자가 같으면 합쳐짐
// -> 조건3: 이미 한번 합쳐진 블록이라면 결합 불가
//자료구조:
//합쳐진 블록의 인덱스를 갖고 있을 리스트
//시간복잡도:
//시간이 매우 짧기 때문에 이동하는 시간을 거의 없는 것으로 만들어야함
//하지만 depth가 5이기 때문에 충분할 것이라고 판단

public class Easy2048 {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static ArrayList<int[]> fusionBlock;
    static ArrayList<int[]> blockSeq;
    static int[][] matrix;
    static int n;
    static int maxBlock = -1;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.valueOf(br.readLine());
        StringTokenizer st;
        matrix = new int[n][n];
        fusionBlock = new ArrayList<>();
        blockSeq = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        back(0);
        System.out.println(maxBlock);
    }

    public static void back(int depth) {
        if (depth == 5) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] != 0) {
                        if (maxBlock < matrix[i][j]) {
                            maxBlock = matrix[i][j];
                        }
                    }
                }
            }
            return;
        }
        for (int i = 0; i < 4; i++) {
            blockSeq = new ArrayList<>();
            if (i == 0) {
                for (int j = 0; j < n; j++) {
                    for (int h = n - 1; h >= 0; h--) {
                        if (matrix[j][h] != 0) {
                            blockSeq.add(new int[]{j, h});
                        }
                    }
                }
            } else if (i == 1) {
                for (int j = 0; j < n; j++) {
                    for (int h = 0; h < n; h++) {
                        if (matrix[j][h] != 0) {
                            blockSeq.add(new int[]{j, h});
                        }
                    }
                }
            } else if (i == 2) {
                for (int j = 0; j < n; j++) {
                    for (int h = n - 1; h >= 0; h--) {
                        if (matrix[h][j] != 0) {
                            blockSeq.add(new int[]{h, j});
                        }
                    }
                }
            } else if (i == 3) {
                for (int j = 0; j < n; j++) {
                    for (int h = 0; h < n; h++) {
                        if (matrix[h][j] != 0) {
                            blockSeq.add(new int[]{h, j});
                        }
                    }
                }
            }
            int[][] matrixCopy = new int[n][n];
            for (int z = 0; z < n; z++) {
                for (int c = 0; c < n; c++) {
                    matrixCopy[z][c] = matrix[z][c];
                }
            }
            fusionBlock = new ArrayList<>();
            for (int j = 0; j < blockSeq.size(); j++) {
                int[] cur = blockSeq.get(j);
                move(cur[0], cur[1], i, cur[0] + dx[i], cur[1] + dy[i], cur[0], cur[1]);
            }
            back(depth + 1);
            matrix = matrixCopy;
        }
    }

    public static void move(int x, int y, int vector, int nx, int ny, int bx, int by) {
        if (ny >= n || ny < 0 || nx >= n || nx < 0) {
            return;
        }
        //끝인지 판별
        boolean check = false;
        if (vector == 0) {
            if (ny == n - 1) {
                check = true;
            }
        } else if (vector == 1) {
            if (ny == 0) {
                check = true;
            }
        } else if (vector == 2) {
            if (nx == n - 1) {
                check = true;
            }
        } else if (vector == 3) {
            if (nx == 0) {
                check = true;
            }
        }
        if (matrix[nx][ny] != 0 || check) {
            if (matrix[nx][ny] == 0) {
                matrix[nx][ny] = matrix[x][y];
                matrix[x][y] = 0;
                return;
            }
            //결합
            if (matrix[nx][ny] == matrix[x][y] && !(containsArray(fusionBlock, new int[]{nx, ny}))) {
                matrix[nx][ny] *= 2;
                matrix[bx][by] = 0;
                fusionBlock.add(new int[]{nx, ny});
            } else {
                matrix[bx][by] = matrix[x][y];
                if (bx == x && by == y) {
                    return;
                }
            }
            matrix[x][y] = 0;
            return;
        }
        move(x, y, vector, nx + dx[vector], ny + dy[vector], nx, ny);
    }

    private static boolean containsArray(ArrayList<int[]> list, int[] array) {
        for (int[] element : list) {
            if (Arrays.equals(element, array)) {
                return true;
            }
        }
        return false;
    }
}

조건문으로 어느 사분면에 해당하는지 확인하는 것이 중요함

아이디어, 자료구조, 시간 복잡도

주석참고

1. 백트랙킹을 수행하는데 이동 방향에 따라 block을 다른 순서로 넣어준다.(이동 방향 반대 순서부터 진행해야하기 때문)
2. 그리고 이동을 진행한다.
3. 이동에는 많은 조건들이 있다.
4. 중요한 점은 이것이 한번 결합이 된 것인지 체크하는 과정이다.
5. list에 결합된 곳에 index를 담아서 체크했다.
6. depth 5에 다다랐을때 MAX 값을 갱신한다.

걸린 시간

3,4 시간?

총평

골드2 치고는 아이디어를 생각하는 것은 매우 쉬운 편이었다고 생각한다.
예를 들어서 딱 보았을 때 백트랙킹과 DFS를 사용할 수 있는 것을 떠올 릴 수 있다.
하지만 이동하는 것에 있어서 조건이 매우 까다롭다.
구현이 어려운 문제였다고 할 수 있다.