[ 백준 / 12100번 ] Gold II - 2048 (Easy) : Solved by java

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

진짜 이렇게 하나 풀겠다고 눈도 안깜빡이고 있으니 눈이 나빠지지...  코딩은 신체 건강을 해치는 지름길이다..

문제

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

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

<그림 1>	<그림 2>	<그림 3>

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

<그림 4>	<그림 5>	<그림 6>	<그림 7>

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

<그림 8>	<그림 9>

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

<그림 10>	<그림 11>	<그림 12>	<그림 13>

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

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

<그림 14>	<그림 15>

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

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

입력

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

출력

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

 

[ 풀이 코드 ] 

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

public class 이공사팔Easy {
	static int ans, N;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		int[][] arr = new int[N][N];
		ans = 0;
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				ans = arr[i][j] > ans ? arr[i][j] : ans;
			}
		} // 입력 완료
		check(ans, arr, 0);// 방향(상1하2좌3우4),최대값,베열, 이동 수
		System.out.println(ans);

	}

	private static void check(int max, int[][] arr, int n) {
		
		if (n == 5) {
			ans = max > ans ? max : ans;
			return;
		}
		// 이제 뒹굴 데굴
		int[][] tmp = new int[N][N];
		for (int i = 0; i < N; i++) {
			System.arraycopy(arr[i], 0, tmp[i], 0, N);
		} // 바꿀꺼니꼐 복사해두자
			// D = 1;
		int m = max;
		boolean[][] v = new boolean[N][N]; // 이게 바뀐건지 안바뀐 건지 체크
		for (int j = 0; j < N; j++) {// 열마다 반복
			int a = 0;
			for (int i = 0; i < N; i++) {				
				if (arr[i][j] != 0) {
					if (a > 0 && !v[a - 1][j] && arr[a - 1][j] == arr[i][j]) {
						v[a - 1][j] = true;
						arr[a - 1][j] *= 2;
						m = arr[a - 1][j] > m ? arr[a - 1][j] : m;
					} else {
						arr[a++][j] = arr[i][j];
					}
				}
			} // 밑에 쌓아주기
			for (; a < N; a++) {
				arr[a][j] = 0;
			}
		}
		check(m, arr, n + 1);// 최대값,베열, 이동 수
		// 하
		for (int i = 0; i < N; i++) {
			System.arraycopy(tmp[i], 0, arr[i], 0, N);
		} // 바꿀꺼니꼐 복사해두자
		m = max;
		v = new boolean[N][N]; // 이게 바뀐건지 안바뀐 건지 체크
		for (int j = 0; j < N; j++) {
			int a = N - 1;
			for (int i = N - 1; i >= 0; i--) {
				if (arr[i][j] != 0) {
					if (a < N - 1 && !v[a + 1][j] && arr[a + 1][j] == arr[i][j]) {
						v[a + 1][j] = true;
						arr[a + 1][j] *= 2;
						m = arr[a + 1][j] > m ? arr[a + 1][j] : m;
					} else {
						arr[a--][j] = arr[i][j];
					}
				}
			}
			for (; a >= 0; a--) {
				arr[a][j] = 0;
			}
		}
		check(m, arr, n + 1);// 최대값,베열, 이동 수
		// 좌
		for (int i = 0; i < N; i++) {
			System.arraycopy(tmp[i], 0, arr[i], 0, N);
		} // 바꿀꺼니꼐 복사해두자
		m = max;
		v = new boolean[N][N]; // 이게 바뀐건지 안바뀐 건지 체크
		for (int i = 0; i < N; i++) {
			int a = 0;
			for (int j = 0; j<N; j++) {
				if (arr[i][j] != 0) {
					if (a > 0 && !v[i][a-1] && arr[i][a-1] == arr[i][j]) {
						v[i][a-1] = true;
						arr[i][a-1] *= 2;
						m = arr[i][a-1] > m ? arr[i][a-1] : m;
					} else {
						arr[i][a++] = arr[i][j];
					}
				}
			}
			for (; a < N; a++) {
				arr[i][a] = 0;
			}
		}
		check(m, arr, n + 1);// 최대값,베열, 이동 수
		// 우
		for (int i = 0; i < N; i++) {
			System.arraycopy(tmp[i], 0, arr[i], 0, N);
		} // 바꿀꺼니꼐 복사해두자
		m = max;
		v = new boolean[N][N]; // 이게 바뀐건지 안바뀐 건지 체크
		for (int i = 0; i < N; i++) {
			int a = N - 1;
			for (int j = N - 1; j >= 0; j--) {
				if (arr[i][j] != 0) {
					if (a < N - 1 && !v[i][a+1] && arr[i][a+1] == arr[i][j]) {
						v[i][a+1] = true;
						arr[i][a+1] *= 2;
						m = arr[i][a+1] > m ? arr[i][a+1] : m;
					} else {
						arr[i][a--] = arr[i][j];
					}
				}
			}
			for (; a >= 0; a--) {
				arr[i][a] = 0;
			}
		}
		check(m, arr, n + 1);// 최대값,베열, 이동 수
	}
}

 

[ 풀이 ] 

코드 자체는 그리 어렵지 않지만, 이놈의실수, 이놈의 헷갈림 이게 문제다...

main 의 코드는 간단하다, 입력받고, dfs부르고, ans를 출력한다. N과 ans는 static 변수로 선언해준다. 

ㄹ

dfs 코드로 들어와서 먼저 탈출조건을 적어둔다. 5번 이상 움직이지 말라고 하였으므로, 0~4까지 해서 5번 이상이면 ㄱreturn 한다. 

 

먼저 우선 값을 따로 저장해 두어야 한다. 원본 배열은 따로 가지고 있어야, 상하좌우 이동 후 값을 처리할 수 있다. 

( 근데 지금 생각해보니 그냥 새로 선언해줄걸 그랬다 그럼 바꾼 이후 값 0으로 안바꿔 줘도 되는데...

출력해야 할 값은 max값이므로, max를 적어준다. 그리고 이미 바꾼 값이면 바꾸면 안되니까 v를 따로 선언해 준다. 

그리고 반복문을 돌면서 배열을 만들어 준다.  a가 쌓을 수 있게 도와주는 값이 된다. 

이렇게 구현하면, 만약에 진행하다가 이전에 적어둔 값이랑 현재의 값이 동일하면 이를 합쳐주게 된다. 

진행을 하다가, 이전에 적어둔 arr[a-1][j]와 같고, 이전에 이 값은 바뀌어 진 적이 없으면 

arr[a-1][j] 는 두배가 되고, max도 갱신시켜준다. // 지금 또 생각한건데 m을 초기화시켜줄 필요가 없네, 

그리고 a 이후의 값은 0으로 만들어 준다. 

그리고 현재의 배열을 가지고 다시 dfs를 돌면 된다. 

방금 설명은 상의 경우를 말한거고 

이제 그 이후로 하좌우를 모두 구현해주면

끝이나는 문제이지만 간단해 보이지만 디테일한 조건을 생각해 줘야 하는 그런 간단하고 복잡한 그런 문제..

점점 풀면서 더 어려워하는 기분이다.. 한번에 쓱 풀린 적이 없어..