백준 - 2048 (Easy) (12100)

1. 문제

문제 링크

2.풀이

2-1. 조건

1. 한 번의 이동에서 이미 합쳐진 블록은 다른 블록과 합쳐질 수 없다. (연달아 합쳐질 수 없다)
2. 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 방향의 칸이 먼저 합쳐진다.

2-2 풀이

이 문제는 완전 탐색을 통해서 얻을 수 있는 최대값을 출력하면 되는 문제입니다.
블록들을 네가지의 방향으로 최대 5번 이동시킬 수 있기 때문에
경우의 수는 4^5 = 1024가지의 경우의 수가 나오고
각 경우의 수마다 블록의 이동과 충돌을 구현하면 답을 구할 수 있습니다.

그렇다면 문제는 충돌의 구현인데 어떻게 해야 쉽게 구현할 수 있을까요?
많은 방법이 있겠지만 저는 큐를 이용해서 구현해보겠습니다.
왜냐하면 2번 조건을 충족시켜주려면 순서를 생각해 줘야 하는데
큐 자료구조가 그 순서의 대한 조건을 충족시키기 적합하기 때문입니다.

그렇다면 한 가지 예를 들어 북쪽으로 이동했을 때를 구현해보겠습니다.

블록이 위 그림처럼 있다고 가정해봅시다.
북쪽으로 이동하니 위에서부터 블록들을 차례대로 큐에 넣어줍시다.

그러면 위 그림 같은 상태가 됩니다.(그림판을 잘 못 다룹니다...양해 부탁드립니다.)
이 상태에서 큐에서 차례대로 poll해서 위에서부터 채워주면 되겠죠?

처음엔 빈 블록이니 그대로 들어갑니다.

이번엔 블록이 이미 존재합니다.
큐에서 빼온 블록과 동일한 블록이니까 합쳐줍니다.

마지막으로 큐에서 블록을 빼왔는데 동일하지 않습니다.
다음 위치에 블록을 위치시킵니다.
그러면 최종적으로 이러한 모습이 되겠네요.

이 과정을 각 컬럼마다 진행하면 북쪽 이동을 구현할 수 있고
이와 같은 매커니즘으로 동, 남, 서쪽 이동을 구현할 수 있겠죠?

다시 총 정리를 해보면
1. 백트래킹으로 경우의 수마다 블록을 북,동,남,서로 이동
2. 백트래킹을 빠져나오면 이전 상황으로 복귀
3. 모든 경우의 수를 시뮬레이션 하면서 만들 수 있는 가장 큰 블록 출력

3. 전체 코드

package Main;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N;
	static int[][] m;
	
	static int max(int depth) {
		// 기저 사례 -> 5번 이동했을 때 가장 큰 블록 리턴
		if (depth == 5) {
			int ret = 0;
			
			for (int i = 0; i < N; i++)
				for (int j = 0; j < N; j++)
					ret = Math.max(ret, m[i][j]);
			
			return ret;
		}
		
		int ret = 0;
		int[][] tmp = new int[N][N];
		copy(tmp, m); // 현재 상황 기억
		
		for (int dir = 0; dir < 4; dir++) {
			crash(dir); // 블럭 충돌
			ret = Math.max(ret, max(depth + 1));
			copy(m, tmp); // 백트래킹을 빠져나오면 이전 상황으로 복귀 (2번 계획)
		}
		
		return ret;
	}
	
	// 블록 이동 함수
	static void crash(int dir) {
		Queue<Integer> q = new LinkedList<>();
		
		switch (dir) {
		case 0: // 북
			for (int c = 0; c < N; c++) {
				// 순서대로 큐에 저장
				for (int r = 0; r < N; r++) {
					if (m[r][c] != 0) {
						q.add(m[r][c]);
						m[r][c] = 0;
					}
				}
				
				int y = 0;
				
				while (!q.isEmpty()) {
					int block = q.poll();
					
					// 비어있다면 그대로 위치 시킴
					if (m[y][c] == 0) {
						m[y][c] = block;
					}
					// 존재했을 때 같다면 합침
					else if (m[y][c] == block) {
						m[y][c] *= 2;
						y++;
					} 
					// 다르다면 다음 공간으로 위치 시킴
					else {
						m[++y][c] = block;
					}
				}
			}
			break;
		case 1: // 동
			for (int r = 0; r < N; r++) {
				for (int c = N - 1; c >= 0; c--) {
					if (m[r][c] != 0) {
						q.add(m[r][c]);
						m[r][c] = 0;
					}
				}
				
				int x = N - 1;
				
				while (!q.isEmpty()) {
					int block = q.poll();
					
					if (m[r][x] == 0) {
						m[r][x] = block;
					}
					else if (m[r][x] == block) {
						m[r][x] *= 2;
						x--;
					} 
					else {
						m[r][--x] = block;
					}
				}
			}
			break;
		case 2: // 남
			for (int c = 0; c < N; c++) {
				for (int r = N - 1; r >= 0; r--) {
					if (m[r][c] != 0) {
						q.add(m[r][c]);
						m[r][c] = 0;
					}
				}
				
				int y = N - 1;
				
				while (!q.isEmpty()) {
					int block = q.poll();
					
					if (m[y][c] == 0) {
						m[y][c] = block;
					}
					else if (m[y][c] == block) {
						m[y][c] *= 2;
						y--;
					} 
					else {
						m[--y][c] = block;
					}
				}
			}
			break;
		case 3: // 서
			for (int r = 0; r < N; r++) {
				for (int c = 0; c < N; c++) {
					if (m[r][c] != 0) {
						q.add(m[r][c]);
						m[r][c] = 0;
					}
				}
				
				int x = 0;
				
				while (!q.isEmpty()) {
					int block = q.poll();
					
					if (m[r][x] == 0) {
						m[r][x] = block;
					}
					else if (m[r][x] == block) {
						m[r][x] *= 2;
						x++;
					} 
					else {
						m[r][++x] = block;
					}
				}
			}
		}
	}
	
	static void copy(int[][] a, int[][] b) {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				a[i][j] = b[i][j];
	}
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine());
		m = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			String[] s = br.readLine().split(" ");
			for (int j = 0; j < N; j++)
				m[i][j] = Integer.parseInt(s[j]);
		}
		
		bw.write(max(0) + "");
		bw.close();
	}
}