2 분 소요

문제

문제 바로가기

입력

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

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

접근방법

먼저, 상, 하, 좌, 우로 이동하는 함수를 구현해야 한다.

이동 가능 여부를 판단하기 위해서는 다음과 같은 조건을 검사해야 한다.

  • 이동하려는 칸이 보드 내부에 존재하는지?
  • 이동하려는 칸이 비어있는지?
  • 이동하려는 칸과 합쳐질 수 있는지?

이동 할 때는 이전 칸의 값을 이동하려는 칸으로 복사한 후, 이전 칸의 값을 0으로 설정한다. 만약 같은 숫자가 이어진 경우에는 합쳐지는 것으로 간주하여 합쳐진 블록의 값을 2배로 변경하고, 이전 칸의 값을 0으로 설정한다.

위에서 구현한 이동 함수를 이용하여 완전탐색 방식으로 모든 경우를 검사한다.

이동 함수를 호출하기 전에 현재 보드의 값을 복사하고, 네 방향으로 이동하는 경우를 각각 호출해야 한다.

depth가 5인 경우에는 더 이상 탐색을 진행하지 않고 현재 보드에서 가장 큰 블록의 값을 구하여 max와 비교해준다. 이 과정을 반복하여 모든 경우를 탐색한 후에 가장 큰 블록의 값을 출력하면 된다.

풀이

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

public class Main {
    static int N;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int max = 0;
    public static void main(String[] args) 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());
            }
        }

        find(0, map);

        System.out.println(max);
    }

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

    public static void find(int depth, int[][] map) {
        if(depth == 5) {
            int tmp = maxValue(map);
            max = Math.max(max, tmp);
            return;
        }

        for(int i = 0; i < 4; i++) {
            int[][] copy = new int[N][N];
            for(int k = 0; k < N; k++) {
                copy[k] = map[k].clone();
            }
            boolean[][] check = new boolean[N][N];
            move(i, copy, check);
            find(depth+1, copy);
        }
    }

    public static void move(int d, int[][] map, boolean[][] check) {
        switch (d) {
            case 0:
                for(int i = 0; i < N; i++) {
                    for(int j = 0; j < N; j++) {
                        dfs(i, j, 0, map, check);
                    }
                }
                break;
            case 1:
                for(int i = N-1; i >= 0; i--) {
                    for(int j = 0; j < N; j++) {
                        dfs(i, j, 1, map, check);
                    }
                }
                break;
            case 2:
                for(int i = 0; i < N; i++) {
                    for(int j = 0; j < N; j++) {
                        dfs(j, i, 2, map, check);
                    }
                }
                break;
            case 3:
                for(int i = N-1; i >= 0; i--) {
                    for(int j = 0; j < N; j++) {
                        dfs(j, i, 3, map, check);
                    }
                }
                break;
        }
    }

    public static void dfs(int x, int y, int d, int[][] map, boolean[][] check) {
        int tx = x + dx[d];
        int ty = y + dy[d];
        if(tx >= 0 && ty >= 0 && tx < N && ty < N) {
            if(map[tx][ty] == 0) {
                map[tx][ty] = map[x][y];
                map[x][y] = 0;
                dfs(tx, ty, d, map, check);
            }
            else if(map[tx][ty] == map[x][y] && !check[tx][ty]) {
                map[tx][ty] *= 2;
                check[tx][ty] = true;
                map[x][y] = 0;
            }
        }
    }
}

댓글남기기

참고