백준 12100 : 2048(Easy)

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

[ 문제풀이 ]

이번에도 마찬가지로 전형적인 시뮬레이션 문제이다. 2048 게임은 워낙 유명하기 때문에 문제를 이해하는 데는 어려움이 없을 것이다.

​4방향으로 이동해야하는 문제는 4방향 함수를 모두 구현하는 것보다 맵을 회전하여 4개를 만든 후 한 가지 방향으로 이동시키는 메서드를 구현하는 것이 구현하기에 훨씬 편할 것이다.

삼성 문제는 시간 복잡도가 넉넉하기 때문에 맵을 회전시킨다하여도 크게 상관이 없다.

​

나는 블록들을 위로 이동하는 메서드를 하나 구현하였고 왼쪽/오른쪽/아래로 이동하는 것은 맵을 90, 180, 270도로 회전시켜 위로 이동하는 것으로 구현하였다.

​이때 조심해야 할 점은 이동시키면서 블록이 합쳐질 수도 있기 때문에 이동할 때마다 새로운 2차원 맵을 매개변수로 넘겨줘야 한다는 것이다.

똑같은 2차원 맵을 넘겨준다면 같은 주소이기 때문에 원하는 값을 얻을 수 없다. 깊은 복사와 얕은 복사의 차이다.

​

마지막으로 블록을 위로 이동시키는 메서드가 구현하기 까다로울 수도 있을 것이다.

적합한 자료구조를 잘 활용한다면 쉽게 해결할 수 있다. 나는 덱(Deque)을 사용하여 해결하였다. 위에서부터 아래로 내려가면서 아래의 조건만 확인해주면 된다.

check라는 변수를 통해 현재의 블록 위로 합칠 수 있는 블록이 있는지를 판단하였다.

check == false : 합칠 수 있는 블록이 없기 때문에 덱에 삽입해 줌, check = true;
check == true : 1. 덱의 제일 앞 원소가 현재 블록과 같으면 두 블록을 합쳐줌, check = false
                2. 덱의 제일 앞 원소가 현재 블록과 다르면 덱에 삽입해 줌

전체 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int N, answer;
	static Deque<Integer> deque;
	
	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		
		int[][] map = new int[N][N];
		for (int i = 0; i < N; ++i) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		deque = new LinkedList<>();
		
		simulation(0, map);
		
		bw.write(answer + "\n");
		bw.flush();bw.close();br.close();
	}

	public static void simulation(int cnt, int[][] map) {
		if (cnt == 5) {
			answer = Math.max(answer, get_MaxBlock(map));
			return;
		}

		int[][] temp;
		
		//블록을 움직이는 메서드를 하나만 구현하기 위해 map을 회전시킴
		for (int d = 0; d < 4; ++d) {
			temp = new int[N][N];
			//d = 0 : 회전없이 바로 위로 올림
			if (d == 0) {
				for (int i = 0; i < N; ++i) {
					for (int j = 0; j < N; ++j) {
						temp[i][j] = map[i][j];
					}
				}
				moveUpBlock(cnt, temp);
			} 
			//d != 0 : 시계방향 90, 180, 270도로 회전
			else {
				rotation(cnt, map, temp);
			}
		}
	}

	/**
	 * 시계방향으로 90도 회전하여 블록들을 위로 올림
	 * 총 3번을 회전시켜야 하기 때문에 회전시킨 temp -> map으로 다시 옮김
	 */
	public static void rotation(int cnt, int[][] map, int[][] temp) {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				temp[j][N - i - 1] = map[i][j];
			}
		}

		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				map[i][j] = temp[i][j];
			}
		}

		moveUpBlock(cnt, temp);
	}

	public static void moveUpBlock(int cnt, int[][] map) {
		//모든 열을 위로 올려봄, 블록을 관리하기 위해 덱(Deque)를 사용
		for (int j = 0; j < N; ++j) {
			boolean check = false; //현재 블록 위쪽에 합치지 않은 블록이 있는지 판단
			
			for (int i = 0; i < N; ++i) {
				if (map[i][j] == 0) continue;
				
				//현재 위쪽에 합치지 않은 블록이 없으면 덱의 제일 앞에 넣어주고 true로 변경
				if (!check) {
					deque.addFirst(map[i][j]);
					check = true;
				} else {
					//덱의 제일 앞의 값이 현재 블록과 같은 값이면 합쳐주고 false로 변경
					if (deque.peek() == map[i][j]) {
						deque.poll();
						deque.addFirst(map[i][j] * 2);
						check = false;
					} 
					//합칠 수 없으면 덱의 제일 앞에 넣어줌
					else {
						deque.addFirst(map[i][j]);
					}
				}
			}
			
			int size = deque.size();
			
			//덱에 있는 원소를 차례대로 맵에 옮겨주고 나머지는 0으로 처리
			for (int i = 0; i < N; ++i) {
				if (i < size) {
					map[i][j] = deque.pollLast();
				} else {
					map[i][j] = 0;
				}
			}
		}

		simulation(cnt + 1, map);
	}

	public static int getMaxBlock(int[][] map) {
		int maxBlock = 0;

		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				maxBlock = Math.max(max_Block, map[i][j]);
			}
		}

		return maxBlock;
	}
}