Baekjoon 12100 2048(Easy) JAVA

12100번: 2048 (Easy)

문제

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

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

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

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

 

조건

[입력]

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

 

[출력]

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

 

풀이

해당 문제는 2048 게임을 5회 했을 때 최댓값을 구하는 문제다. 다만 쉬운 버전이라 단계별로 새로운 블록이 추가되지는 않는다.

딱 시뮬레이션 문제였고 순열과 탐색을 이용하여 해결했다. 로직은 아래와 같다.

 

1. 입력값을 입력 처리하면서 map를 경신한다.

2. 5회에 해당하는 순열을 생성한다 (0,0,0,0,0) ~ (4,4,4,4,4)

    1. 순열이 완성되면 체크를 시작한다.

        1. 먼저 기존 배열은 유지해야 하므로 copy_Map를 초기화하고 map를 복사한다.

        2. 경우의 수에 해당하는 방향으로 체크를 진행한다.

            1. 먼저 기준 좌표에서 해당 방향으로 이동을 하면서 값을 더할 수 있는지 체크한다.

                1. 배열 범위가 벗어나면 멈춘다.

                2. 이동하려는 좌표값이 기준 좌표값과 동일하면 더하고 멈춘다.

                3. 이동하려는 좌표값이 기준 좌표값과 다르면 멈춘다.

            2. 더하기가 끝나면 빈칸을 체크해서 이동시킨다.

                1. 이동하려는 곳이 0이면 기준 좌표값을 이동시키고 기준 좌표값을 경신한다.

                2. 이동하려는 곳이 0이 아니면 멈춘다.

    2. 체크가 완료되면 최댓값을 경신한다.

3. 모든 순열에 대한 체크가 완료되면 결과를 출력한다.

 

최초 문제를 해결하고 4%에서 오류가 나서 질문게시판을 봤지만 해결을 하지 못해 다시 로직을 디버깅하던 중 이동시키는 부분에서 이동된 좌표값을 경신해주지 않아 이동이 한 칸만 일어나는 문제를 체크할 수 있었고 문제를 해결할 수 있었다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N,ans, map[][], copy_Map[][], out[]=new int[5],dy[]= {1,0,-1,0}, dx[]= {0,-1,0,1};
	public static void main(String[] args) throws Exception{
		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());
			}
		}
		perm(0); //순열로 가능한 경우 만들어준다.
		
		System.out.println(ans);
	}
	
	private static void move(int y,int x, int d) { // 더하기가 끝나면 0인공간에 대해 이동시켜준다 
		if(copy_Map[y][x] == 0)
			return;
		int ny = y;
		int nx = x;
		while(true) {
			ny += dy[d];
			nx += dx[d];
			
			if(ny <0|| nx <0 || ny >=N || nx >= N)
				return;
			
			if(copy_Map[ny][nx] == 0) { // 이동 시킴과 동시에 좌표 값도 경신해 준다. 
				copy_Map[ny][nx] = copy_Map[y][x];
				copy_Map[y][x] = 0;
				y = ny;
				x = nx;
			}
			else
				return;
		}
	}
	
	private static void sum(int y,int x, int d) { // 현재 값에서 다음값들을 비교하면서 더할수있으면 더하고 멈춤 
		if(copy_Map[y][x] == 0)
			return;
		int ny = y;
		int nx = x;
		while(true) {
			ny += dy[d];
			nx += dx[d];
			
			if(ny <0|| nx <0 || ny >=N || nx >= N) // 배열 범위 벗어나는 경우 
				return;
			
			if(copy_Map[y][x] == copy_Map[ny][nx]) { // 더하기 
				copy_Map[y][x] += copy_Map[ny][nx];
				copy_Map[ny][nx] = 0;
				return;
			}
			if(copy_Map[ny][nx] != 0) // 더할수 없는 숫자를 만남 
				return;
		}
	}
	
	static void check() { // 기존 배열은 유지해야 함으로 배열을 복사함.
		copy_Map = new int[N][N];
		for (int i = 0; i < N; i++) { //배열 복사 
			for (int j = 0; j < N; j++) {
				copy_Map[i][j] = map[i][j];
			}
		}
		
		for (int t = 0; t < 5; t++) { // 경우의수를 체크하면서 반복문을 돌리는데 방향에따라 반복문의 시작값이 다름. 
			if(out[t] == 0) { // 상 
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						sum(j,i,0); // 먼저 더할수있으면 더한다.
					}
				}
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						move(j,i,2); // 한사이클이 끝나면 빈칸에 이동시켜준다.
					}
				}
			}else if(out[t] == 1) { // 우 
				for (int i = N-1; i >= 0; i--) {
					for (int j = 0; j < N; j++) {
						sum(j,i,1);
					}
				}
				for (int i = N-1; i >= 0; i--) {
					for (int j = 0; j < N; j++) {
						move(j,i,3);
					}
				}
			}else if(out[t] == 2) { // 하 
				for (int i = N-1; i >= 0; i--) {
					for (int j = 0; j < N; j++) {
						sum(i,j,2);
					}
				}
				for (int i = N-1; i >= 0; i--) {
					for (int j = 0; j < N; j++) {
						move(i,j,0);
					}
				}
			}else { // 좌 
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						sum(i,j,3);
					}
				}
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						move(i,j,1);
					}
				}
			}
		}
		
		for (int i = 0; i < N; i++) { // 최대값 갱신.
			for (int j = 0; j < N; j++) {
				ans = Math.max(ans, copy_Map[i][j]);
			}
		}
	}

	static void perm(int index) { // 순열 만드는 부
		if(index == 5) {
			check(); // 가능한 경우가 만들어지면 체크한다.
			return;
		}
		for (int i = 0; i < 5; i++) {
			out[index] = i;
			perm(index+1);
		}
	}
}

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드