[백준] 12100번 2048 (Java)

문제 링크

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

핵심

문제가 긴 구현 문제의 경우 항상 주의사항을 잘 봐야한다. 이 문제의 경우 "한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다" 조건만 생각해서 구현하면 어렵지 않게 해결할 수 있었다.

코드

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

public class Main {
	
	static int[] dr = {-1,0,1,0}, dc = {0,1,0,-1};
	static int N;
	static int[][] board, copy_board;
	static int[] numbers;
	static int answer;
	
	static void permutation(int cnt) { // 2
		if(cnt==numbers.length) {
			copy();
			for(int i=0; i<numbers.length; i++) {
				if(numbers[i]==0) up();
				else if(numbers[i]==1) right();
				else if (numbers[i]==2) down();
				else left();
			}
			int max = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					max = Math.max(max, copy_board[i][j]);
				}
			}
			
			answer = Math.max(answer, max);
			return;
		}
		
		for(int i=0; i<4; i++) {
			numbers[cnt] = i;
			permutation(cnt+1);
		}
	}
	
	static void copy() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				copy_board[i][j] = board[i][j];
			}
		}
	}
	
    // 1
    
	static void up() { 
		Queue<Integer> q = new ArrayDeque<>();
		for(int c=0; c<N; c++) {
			q.clear();
			for(int r=0; r<N; r++) {
				if(copy_board[r][c]>0) q.offer(copy_board[r][c]);
			}
			
			for(int r=0; r<N; r++) {
				if(q.isEmpty()) copy_board[r][c] = 0;
				else {
					int cur = q.poll();
					if(!q.isEmpty() && cur==q.peek()) cur+=q.poll();
					copy_board[r][c] = cur;
				}
			}
		}
		
	}
	
	static void down() {
		Queue<Integer> q = new ArrayDeque<>();
		for(int c=0; c<N; c++) {
			q.clear();
			for(int r=N-1; r>=0; r--) {
				if(copy_board[r][c]>0) q.offer(copy_board[r][c]);
			}
			
			for(int r=N-1; r>=0; r--) {
				if(q.isEmpty()) copy_board[r][c] = 0;
				else {
					int cur = q.poll();
					if(!q.isEmpty() && cur==q.peek()) cur+=q.poll();
					copy_board[r][c] = cur;
				}
			}
		}
	}
	
	static void left() {
		Queue<Integer> q = new ArrayDeque<>();
		for(int r=0; r<N; r++) {
			q.clear();
			for(int c=0; c<N; c++) {
				if(copy_board[r][c]>0) q.offer(copy_board[r][c]);
			}
			
			for(int c=0; c<N; c++) {
				if(q.isEmpty()) copy_board[r][c] = 0;
				else {
					int cur = q.poll();
					if(!q.isEmpty() && cur==q.peek()) cur+=q.poll();
					copy_board[r][c] = cur;
				}
			}
		}
	}
	
	static void right() {
		Queue<Integer> q = new ArrayDeque<>();
		for(int r=0; r<N; r++) {
			q.clear();
			for(int c=N-1; c>=0; c--) {
				if(copy_board[r][c]>0) q.offer(copy_board[r][c]);
			}
			
			for(int c=N-1; c>=0; c--) {
				if(q.isEmpty()) copy_board[r][c] = 0;
				else {
					int cur = q.poll();
					if(!q.isEmpty() && cur==q.peek()) cur+=q.poll();
					copy_board[r][c] = cur;
				}
			}
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		N = Integer.parseInt(in.readLine());
		board = new int[N][N];
		copy_board = new int[N][N];
		
		numbers = new int[5];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j=0; j<N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		permutation(0);
		
		System.out.println(answer);
	}

}

1. 상,하,좌,우로 블록들을 미는 메소드를 따로 만들었다. 단순히 반복문만 사용해서 만들어도 무방하지만, 큐를 사용해서 코드 길이를 줄여봤다.
2. 다음으로 5번 이동 후 최댓값을 구하기 위해 상,하,좌,우를 5번 움직이는 모든 경우의 수(1024가지)를 중복순열로 체크해줬다.