[백준] 2048 (EASY) (문제번호 : 12100)

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

오늘도 브루트 뽀쓰

 

먼저 복잡도를 생각해보자

문제에서 추출한 조건 1. 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다  -> 보드의 최대 칸 수는 N^2 개이다. 2. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다.   -> 한번의 이동 시 전체 O(N^2)  -> 한 케이스에서 이동할 수 있는 방향은 4개, 전체 탐색으로 M 번의 이동을 할 경우 O(4^M) 3. 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.  -> 5번 이하이므로 가지의 depth가 5 이하로 나옴 20 * 20 * 4^5 = 약 400,000 번..

이 외에 이 전의 보드를 copy 하거나 Max Value를 뽑기 위한 연산도 들어가지만 O(N^2) 복잡도에 다 포함이 되어 있으므로 생략하도록 한다.

 

이 전의 보드를 copy 하는 방식을 좀 더 개선하고 싶을 때

★ HINT 각각의 방향마다 새로 만든 보드를 가지고 있는 방식도 생각해볼 수 있음. (메모리를 좀 더 사용해서 성능을 개선)

    int [][][] newBoard = new int[4][N][N];

    각 방향마다 새로 만든 보드를 위처럼 3차원 배열에 저장하는 방식으로.. 나중에 이렇게 개선해본다.

 

 

※ 참고로 DP 문제를 위해서는 dfs로 전체탐색을 하는 훈련을 많이 해놓는게 좋다고 본다. (Top-Down 방식을 위해)

   전체 분기 중 부분적으로 중복된 가지들을 메모이제이션 하는게 DP의 핵심이니까.

   이걸 하다보면 자연스럽게 Bottom-Up 방식에 대한 이해가 쉽다. 

   초기의 부분문제는 어떻게 설정할 것인지, 점화식은 어떤식으로 나올 것인지.

 

 

거꾸로 (오른쪽으로 갈때, 왼쪽으로 갈때) 처리는 Dequeue 를 이용해서 pollFirst, pollLast를 이용해서 해결

그외에 어디 방향으로 블록을 이동시키느냐에 따라 시작점을 다르게 처리 한 것 외에는 특별한 건 없음

 

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

/**
 * 2048 (EASY) (문제번호: 12100)
 * 
 * @category Brute Force
 * @since 2020.01.07
 * @author dongha
 */

public class Main {
	public static final int[] dx = { 0, 0, 1, -1 }; // 동서남북
	public static final int[] dy = { 1, -1, 0, 0 };

	public static final int MIN = -1;
	
	public static final int EAST = 0;
	public static final int WEST = 1;
	public static final int SOUTH = 2;
	public static final int NORTH = 3;
	
	public static final int LIMIT = 5;

	public static int[][] board;
	public static int N;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		board = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		bw.write(String.valueOf(move(1)));
		bw.flush();
		bw.close();
	}

	private static int move(int n) {
		int result = MIN;
//		Queue<Integer> q = new LinkedList<>();
		Deque<Integer> dq = new LinkedList<>();
		if (n > LIMIT) {
			result = getMaxValue(board);
			return result;
		}
		int[][] now = getCopiedBoard(board);
		
		// 동서남북 에서 밀 때
		for (int d = 0; d < 4; d++) {
			for(int i = 0;i < N; i++) {
				int x, y;
				// 동서남북 밀 때 첫 위치
				if(d==EAST) {
					x = i;
					y = 0;
				}else if (d==WEST){
					x = i;
					y = N-1;
				}else if (d==SOUTH) {
					x = 0;
					y = i;
				}else {
					x = N-1;
					y = i;
				}
				int nx = x;
				int ny = y;
				for(int j = 0; j < N; j++) {
					// 값이 0이 아니면 q에 배열 값 넣음
					if(board[nx][ny] != 0) {
						dq.add(board[nx][ny]);
						board[nx][ny] = 0;
					}
					nx = nx + dx[d];
					ny = ny + dy[d];
				}
				
				nx = x; ny = y;
				// q에서 빼면서 밀어넣어
				while(!dq.isEmpty()) {
					int val;
					if(d % 1 == 0) { // 오른쪽이나 아래쪽으로 할 때 반대로 할 경우
						val = dq.pollFirst();
					}else {
						val = dq.pollLast();
					}
					// 현재 위치 값 0 이면 일단 넣어
					if(board[nx][ny] == 0) {
						board[nx][ny] = val;
					} else if (board[nx][ny] == val){
						// 이전 값이랑 뽑은 값이 같으면 두개 더해
						board[nx][ny] += val;
						nx += dx[d]; ny += dy[d];
					} else {
						// 다른 값이면 다음 자리에 값을 넣음
						nx += dx[d]; ny += dy[d];
						board[nx][ny] = val;
					}
				}
			}
			result = Math.max(move(n+1), result);
			// 다른 분기로 가기 전에 이전 보드판으로 초기화
			board = getCopiedBoard(now);
		}

		
		return result;
	}

	private static int getMaxValue(int[][] b) {
		int max = MIN;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				max = Math.max(b[i][j], max);
			}
		}
		return max;
	}

	private static int[][] getCopiedBoard(int[][] org) {
		int[][] copy = new int[N][N];
		for (int i = 0; i < N; i++) {
			copy[i] = Arrays.copyOf(org[i], N);
		}

		return copy;
	}

}