[백준] code.plus(브루트포스 - 비트마스크,JAVA)12100번, 2048 (Easy)

문제 링크

12100번: 2048 (Easy)

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

이 문제에 핵심은

1. 보드를 상, 하, 좌, 우로 이동할 수 있습니다.

2. 이동시 같은 값과 만나면 합쳐집니다.

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

 

이 게임에서는 보드를 상, 하, 좌, 우로 이동시 그 방향으로 한 칸 이동이 아닌 이동 할 수 있으면 계속 이동합니다.

 

재귀를 통해서 보드를 이동하는 모든 경우를 구해서 보드에 최대 값을 구하도록 하였습니다.

 

이동할 때 3가지로 나누어 볼 수 있다.

이동하는 칸이 0일 때 : 이동

이동하는 칸이 같은 값일 때 : 합쳐지기

이동하는 칸이 0이 아닌 다른 값일 때 : 해당 칸 바로 전에서 멈추기

 

보드를 이동할 때 주의점

1. 해당 이동 시 값은 최대 1번 합쳐진다.

2. 합쳐진다는 것은 ×2가 된다는 것이다.

3. 결과에서 최대 5번으로 5번만 이동시켜서 최대값을 얻으면 된다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 2048 보드에 대한 정보를 저장하였습니다.
• 2048게임을 최대 5번 이동하는 gameStart함수를 실행하였습니다.
• 최대 5번 이동했을 때 보드 안에 최대값을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• gameStart함수는 재귀를 통해 2048 게임을 진행합니다.
• gameStart함수는 상, 하, 좌, 우 이동하도록 하였습니다.
• gameStart함수는 0, 같은값, 0이 아닌 다른 값을 만났을 때를 구분하여 보드의 값들을 이동하였습니다.
• boardCheck함수는 현재 보드에서 최대값을 구하는 함수입니다.

 

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

public class Main {
	static int N,result=Integer.MIN_VALUE;
	static int[] dx = {0, 0, -1, 1};	//상,하,좌,우 x값 변경값
	static int[] dy = {-1, 1, 0, 0};	//상,하,좌,우 y값 변경값
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		int[][] board = new int[N][N];
        	//입력되는 보드 값 저장
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			for(int j=0;j<N;j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		gameStart(0, board);	//최대 5번 이동하는 모든 경우 구하는 함수 실행
		bw.write(result + "\n");	// 보드 최대값 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//보드 상,하,좌,우 최대 5번 이동시켜 최대값 구하는 재귀 함수
	static void gameStart(int count, int[][] board) {
		if(count==5) {		//5번 이동했을 때
			boardCheck(board);	//보드 안에 최대값 비교
			return;
		}
        	//'상' 이동시
		int[][] temp = new int[N][N];
		boolean[][] sum = new boolean[N][N];
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				int x = j;
				int y = i;
				boolean check = false;
				while(y>0) {
					x += dx[0];
					y += dy[0];
					if(temp[y][x]==0)	//만나는 값 0일 때
						continue;
					if(temp[y][x] == board[i][j] && !sum[y][x]) {	//만나는 값 같은 값일 때
						temp[y][x] = board[i][j] * 2;
						check = true;
						sum[y][x] = true;
						break;
					}else {	//만나는 값 0이 아닌 다른 값일 때
						x -= dx[0];
						y -= dy[0];
						break;
					}
				}
				if(!check)
					temp[y][x] = board[i][j];
			}
		}
		gameStart(count+1, temp);
        	//'하' 이동시
		temp = new int[N][N];
		sum = new boolean[N][N];
		for(int i=N-1;i>=0;i--) {
			for(int j=0;j<N;j++) {
				int x = j;
				int y = i;
				boolean check = false;
				while(y<N-1) {
					x += dx[1];
					y += dy[1];
					if(temp[y][x]==0)	//만나는 값 0일 때
						continue;
					if(temp[y][x] == board[i][j] && !sum[y][x]) {	//만나는 값 같은 값일 때
						temp[y][x] = board[i][j] * 2;
						check = true;
						sum[y][x] = true;
						break;
					}else {	//만나는 값 0이 아닌 다른 값일 때
						x -= dx[1];
						y -= dy[1];
						break;
					}
				}
				if(!check)
					temp[y][x] = board[i][j];
			}
		}
		gameStart(count+1, temp);
        	//'좌' 이동시
		temp = new int[N][N];
		sum = new boolean[N][N];
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				int x = j;
				int y = i;
				boolean check = false;
				while(x>0) {
					x += dx[2];
					y += dy[2];
					if(temp[y][x] == 0)	//만나는 값 0일 때
						continue;
					if(temp[y][x] == board[i][j] && !sum[y][x]) {	//만나는 값 같은 값일 때
						temp[y][x] = board[i][j] * 2;
						sum[y][x] = true;
						check = true;
						break;
					}else {	//만나는 값 0이 아닌 다른 값일 때
						x -= dx[2];
						y -= dy[2];
						break;
					}
				}
				if(!check)
					temp[y][x] = board[i][j];
			}
		}
		gameStart(count+1, temp);
        	//'우' 이동시
		temp = new int[N][N];
		sum = new boolean[N][N];
		for(int i=0;i<N;i++) {
			for(int j=N-1;j>=0;j--) {
				int x = j;
				int y = i;
				boolean check = false;
				while(x<N-1) {
					x += dx[3];
					y += dy[3];
					if(temp[y][x] == 0)	//만나는 값 0일 때
						continue;
					if(temp[y][x] == board[i][j] && !sum[y][x]) {	//만나는 값 같은 값일 때
						temp[y][x] = board[i][j] * 2;
						sum[y][x] = true;
						check = true;
						break;
					}else {	//만나는 값 0이 아닌 다른 값일 때
						x -= dx[3];
						y -= dy[3];
						break;
					}

				}
				if(!check)
					temp[y][x] = board[i][j];
			}
		}
		gameStart(count+1, temp);
	}
    	//현재 보드에 최대값 구하는 함수
	static void boardCheck(int[][] board) {
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(board[i][j]==0)
					continue;
				else
					result = Math.max(result, board[i][j]);
			}
		}
		return;
	}
}