백준 12100번: 2048(easy)

문제 설명

• 2048 게임을 구현하는 문제입니다.

접근법

• 5번의 시도횟수를 모두 실행해봐야 정답을 알 수 있다고 생각했습니다.
  • 순열을 통해 해당 기능을 구현했습니다.
• d방향으로 전체 블록을 올바르게 이동 및 합체시킬 수 있으면 이 문제를 풀 수 있다고 생각했습니다.
  • 블록을 하나씩 d방향으로 옮기는 게 곧 전체 블록을 d방향으로 옮기는 거라고 생각했습니다.
• 해당 이동에서 한번 합쳐진 블록은 또 합쳐질 수 없기 때문에 이를 표시하는 변수가 필요할 거라 생각했습니다.
  • pos객체에 int x, int y, boolean unioned 를 사용하는 것도 고려했지만 더 직관적으로 풀기 위해 board와 동일한 2차원 배열에 합체여부를 표시했습니다.

pseudocode

permu(){
	if(5개의 이동방향이 결정되면){
	board의 복제본 copyBoard를 만듭니다.
    5개의 이동방향에 대해 Go(전체 board를 해당 방향으로 미는 행위)를 실행합니다.
    board의 값을 모두 돌면서 가장 큰 수를 갱신합니다.
	}
}
Go(방향, 이미 합쳐졌는지를 판단하는 배열, 보드){
	// 두 경우가 나뉘는 이유는 똑같은 수가 세 개인 경우 이동하려는 쪽의 칸으로 먼저 합쳐져야 한다는 조건이 있기 때문입니다.
	if(오른쪽 or 아래){
    	(N,N) -> (0,0)순서로 모든 블록에 대해 OneBlockMove를 실행합니다.
    } else if(왼쪽 or 위){
    	(0,0) -> (N,N)순서로 모든 블록에 대해 OneBlockMove를 실행합니다.
    }

}

// 하나의 블록을 해당 방향으로 움직이는 메서드 입니다.
OneBlockMove(블록의 좌표, 블록의 값, 방향, 이미 합쳐졌는지를 판별하는 배열, 보드){ 
	while(){ // 한칸씩 전진합니다.
    	(nx,ny)는 다음칸의 좌표입니다.
    	다음칸이 보드를 벗어난다면 그만둡니다.
        다음칸이 빈칸이 아니라면(!=0) 반복문을 종료합니다.
        다음칸이 빈칸이라면 (x,y)의 값을 (nx,ny)로 옮깁니다.
        x와 y를 nx와 ny로 갱신시킵니다.
    }
    if(이동시킨 블록의 값과 부딪힌 블록의 값이 같으면서 부딪힌 블록이 합쳐져서 생긴 블록이 아니라면){
    	두 블록을 합칩니다.
        해당 블록은 합쳐저서 생긴 블록이라는 걸 표시합니다.
    }
}

정답

import java.util.*;

public class Main {
	static int[] dx = { 0, 1, 0, -1 }; // 오른쪽,아래,왼쪽,위
	static int[] dy = { 1, 0, -1, 0 };
	static int N;
	static int[][] board;
	static int max_num = 0;
	static int[] d_order = new int[5];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		board = new int[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = sc.nextInt();
			}
		}

		permu(0);

		System.out.println(max_num);

	}

	// 5번의 방향을 결정합니다.
	public static void permu(int depth) {
		if (depth == 5) {
			int[][] copyBoard = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					copyBoard[i][j] = board[i][j];
				}
			}
			for (int i = 0; i < 5; i++) {
				Go(d_order[i], new boolean[N][N], copyBoard);
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					max_num = Math.max(max_num, copyBoard[i][j]);
				}
			}
			return;
		}
		for (int i = 0; i < 4; i++) {
			d_order[depth] = i;
			permu(depth + 1);
		}
	}

	// 하나의 블록을 d방향으로 이동시키는 메서드입니다.
	public static void OneBlockMove(int x, int y, int val, int d, boolean[][] v, int[][] board) {
		int nx = 0;
		int ny = 0;
		while (true) { // 다음칸으로 이동이 가능할때까지 계속됩니다.
			// (nx,ny)는 다음칸 입니다.
			nx = x + dx[d];
			ny = y + dy[d];
			if (0 > nx || nx >= N || 0 > ny || ny >= N) return; // 다음칸이 보드위에 없다면 이동이 불가능합니다.
			if (board[nx][ny] != 0) break; // 0이 아닌 값을 만났으면 일단 멈춥니다.

			// (x,y)에 있던 값을 (nx,ny)로 이동시킵니다.
			board[x][y] = 0;
			board[nx][ny] = val;
			// (x,y)를 갱신시킵니다.
			x = nx;
			y = ny;
		}

		// board[x][y]와ㅣ board[nx][ny]가 합쳐질 수 있는지 확인합니다.
		if (val == board[nx][ny] && !v[nx][ny]) { // board[x][y]와 board[nx][ny]의 값이 같으며, board[nx][ny]가 합쳐서 만들어진 수가 아니라면
			// 합칩니다.
			board[nx][ny] = 2 * val;
			board[x][y] = 0;
			// 합쳤다는 표시를 남깁니다.
			v[nx][ny] = true;
		}
	}

	// 블록 하나하나에 대해 OneBlockMove를 실행해 전체 블록을 모두 이동시킵니다.
	public static int[][] Go(int d, boolean[][] v, int[][] board) {
		if (d == 0 || d == 1) { // 똑같은 수가 세 개인 경우 이동하려는 쪽의 칸이 먼저 합쳐지기 때문에 오른쪽과 아래는 오른쪽아래에서부터 OneBlockMove를 해야 합니다.
			for (int i = N - 1; i >= 0; i--) {
				for (int j = N - 1; j >= 0; j--) {
					OneBlockMove(i, j, board[i][j], d, v, board);
				}
			}
		} else {
			for (int i = 0; i < N; i++) { // 왼쪽과 위는 왼쪽위에서부터 OneBlockMove를 실행하면 됩니다.
				for (int j = 0; j < N; j++) {
					OneBlockMove(i, j, board[i][j], d, v, board);
				}
			}

		}
		return board;
	}
}