[백준: Java] 12100 - 2048(Easy)

[문제]

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

오랜만에 높은 난이도의 문제를 풀어보았는데, 전혀 Easy하지 않았습니다.

 

풀이 방식 자체는 어렵지 않게 떠올렸는데, 보드를 조작하는 과정에서 원상 복귀하는 것을 고려하지 않아 디버깅에 3시간을 헤맨 문제입니다.

 

또한 생각한 풀이가 너무나도 삼성스럽길래 찾아보니 기출문제가 맞았습니다.

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

이 문제와 유사한 거 같습니다.

---

[초기화]

public class BOJ_12100_2048Easy {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n;
	static int[][] grid;
	static int[] directions = {1, 2, 3, 4};  // 상좌하우
	static int answer = 0;
	
	public static void main(String[] args) throws IOException {
		n = Integer.parseInt(br.readLine());
		grid = new int[n][n];
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < n; j++)
				grid[i][j] = Integer.parseInt(st.nextToken());
		}
		
		solve();
	}

네 방향으로 움직이기 위한 값을 미리 지정하였습니다.

---

[풀이]

	static void solve() {
		search(0);
		System.out.println(answer);
	}

search 함수를 통해 2048을 시뮬레이션합니다.

 

전달인자는 탐색 횟수를 의미합니다.

	static void search(int cnt) {
		check();
		if(cnt == 5)  // 5번까지 움직였으면 종료
			return;
		
		int[][] backup = new int[n][n];
        for (int i = 0; i < n; i++)
            backup[i] = grid[i].clone(); // grid 상태 저장

		for(int d = 1; d <= 4; d++) {
			move(d);
			search(cnt + 1);
			
			for (int i = 0; i < n; i++)
                grid[i] = backup[i].clone(); // 상태 복구
		}		
	}

1. 함수가 호출될 때마다 최댓값을 찾습니다. 왜냐하면 어떻게 움직였을 때 값이 최대가 되는지 모르기 때문입니다.
2. 최대 5번 움직일 수 있으므로 5번을 움직이게 되면 시뮬레이션을 종료합니다.
   • 종료되기 전에 최댓값을 먼저 찾아야 각 움직임마다 값을 찾을 수 있습니다.
3. 각 움직임에 따라 보드를 직접 조작할 것이기 때문에, 직전 움직임을 취소하고 다른 움직임을 취하기 위해, 원본 보드를 저장합니다.
4. 각 방향에 맞춰 시뮬레이션을 진행합니다.
   • d는 움직임 번호
5. 한 번 움직였으므로 다음으로 넘어갑니다.
6. 방금의 움직임을 취소하고 원상 복귀합니다.

	static void move(int dir) {
		boolean[][] visited = new boolean[n][n];
		
		if(dir == 1) {
			for(int x = 0; x < n; x++)
				for(int y = 1; y < n; y++) {
					int current = y;
					while(current >= 1 && grid[current - 1][x] == 0) {  // 이동시킬 숫자가 있고 다음 이동 방향이 빈 칸일 때
						grid[current - 1][x] += grid[current][x];
						grid[current][x] = 0;
						current--;
					}
					if(current >= 1 && grid[current][x] == grid[current - 1][x] && !visited[current - 1][x]) {  
                        // 이동이 끝나고 다음 이동 방향의 숫자가 동일하고 아직 합쳐지지 않은 숫자라면
						// current를 검사하는 이유는, 단순히 0이 됐을 때 인덱싱 에러가 발생하므로
						grid[current - 1][x] *= 2; // 하나로 합침
						grid[current][x] = 0;
						visited[current - 1][x] = true;
					}
				}
		}
		else if(dir == 2)
			for(int y = 0; y < n; y++)
				for(int x = 1; x < n; x++) {
					int current = x;
					while(current >= 1 && grid[y][current - 1] == 0) {
						grid[y][current - 1] += grid[y][current];
						grid[y][current] = 0;
						current--;
					}
					if(current >= 1 && grid[y][current] == grid[y][current - 1] && !visited[y][current - 1]) {
						grid[y][current - 1] *= 2;
						grid[y][current] = 0;
						visited[y][current - 1] = true;
					}
				}
		else if(dir == 3)
			for(int x = 0; x < n; x++)
				for(int y = n - 2; y > - 1; y--) {
					int current = y;
					while(current <= n - 2 && grid[current + 1][x] == 0) {
						grid[current + 1][x] += grid[current][x];
						grid[current][x] = 0;
						current++;
					}
					if(current <= n - 2 && grid[current][x] == grid[current + 1][x] && !visited[current + 1][x]) {
						grid[current + 1][x] *= 2;
						grid[current][x] = 0;
						visited[current + 1][x] = true;
					}
				}
		else
			for(int y = 0; y < n; y++)
				for(int x = n - 2; x > - 1; x--) {
					int current = x;
					while(current <= n - 2 && grid[y][current + 1] == 0) {
						grid[y][current + 1] += grid[y][current];
						grid[y][current] = 0;
						current++;
					}
					if(current <= n - 2 && grid[y][current] == grid[y][current + 1] && !visited[y][current + 1]) {
						grid[y][current + 1] *= 2;
						grid[y][current] = 0;
						visited[y][current + 1] = true;
					}
				}
	}

방향에 따라 다르게 제어하지만, 로직자체는 동일하므로 동일한 형태의 코드가 반복됩니다.

 

각 번호(1 ~ 4)에 따라 상좌하우로 이동합니다.

 

풀이에서는 상에 해당하는 로직만 풀이하겠습니다.

 

나머지 로직은 동일하니 확인하시면 될 거 같습니다.

 

1. x축(가로)에 따라 이동
2. 가장 상단의 값은 이동할 수 없으므로 그다음 값부터 확인하기 시작(y = 1)
   1. y는 일종의 층(current)으로, 층을 늘려가고(아래로 향하며) 순차적으로 내려가며 바닥(1)까지 검사
   2. 현재 층이 1층 이상이고, 해당 층 기준 앞에 있는 값이 빈 공간이라면 값들을 이동
   3. 앞쪽으로 값을 이동시키고
   4. 기존의 값은 빈 공간으로 변경
   5. 현재 층을 검사했으므로 아래층으로 내려감
3. 이동이 끝나면 값의 상태를 확인하여 취합 시작
   1. 이동된 값이 1층 이상 중 어느 한 곳에 있고, 바로 다음 값이 동일한 값이며, 아직 합치지 않은 값이라면
      1. 앞에 값과 취합
      2. 기존의 값은 빈 공간으로 변경
      3. 취합 상태 변경
   2. 값이 취합된 상태인지 체크해놓지 않으면 동일한 값이 3개가 연속적으로 있을 경우 모두 합쳐지게 됨
4. 모든 로직은 각 방향의 끝보다 한 층 높은 것을 마지막으로 함

저만의 기준을 세운다고 층이라는 애매모호한 표현을 사용했는데, 쉽게 생각하면 이런 식으로 검사를 진행한다고 생각하시면 되겠습니다.

 

이동하려는 방향의 가장 끝 값 다음에 있는 값을 순차적으로 늘려가며, 다시 끝 값까지 이동하여 값을 변경하는 로직입니다.

---

[전체 코드]

package 백준.골드;

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

public class BOJ_12100_2048Easy {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n;
	static int[][] grid;
	static int[] directions = {1, 2, 3, 4};  // 상좌하우
	static int answer = 0;
	
	public static void main(String[] args) throws IOException {
		n = Integer.parseInt(br.readLine());
		grid = new int[n][n];
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < n; j++)
				grid[i][j] = Integer.parseInt(st.nextToken());
		}
		
		solve();
	}
	
	static void move(int dir) {
		boolean[][] visited = new boolean[n][n];
		
		if(dir == 1) {
			for(int x = 0; x < n; x++)
				for(int y = 1; y < n; y++) {
					int current = y;
					while(current >= 1 && grid[current - 1][x] == 0) {  // 이동시킬 숫자가 있고 다음 이동 방향이 빈 칸일 때
						grid[current - 1][x] += grid[current][x];
						grid[current][x] = 0;
						current--;
					}
					if(current >= 1 && grid[current][x] == grid[current - 1][x] && !visited[current - 1][x]) {  
                        // 이동이 끝나고 다음 이동 방향의 숫자가 동일하고 아직 합쳐지지 않은 숫자라면
						// current를 검사하는 이유는, 단순히 0이 됐을 때 인덱싱 에러가 발생하므로
						grid[current - 1][x] *= 2; // 하나로 합침
						grid[current][x] = 0;
						visited[current - 1][x] = true;
					}
				}
		}
		else if(dir == 2)
			for(int y = 0; y < n; y++)
				for(int x = 1; x < n; x++) {
					int current = x;
					while(current >= 1 && grid[y][current - 1] == 0) {
						grid[y][current - 1] += grid[y][current];
						grid[y][current] = 0;
						current--;
					}
					if(current >= 1 && grid[y][current] == grid[y][current - 1] && !visited[y][current - 1]) {
						grid[y][current - 1] *= 2;
						grid[y][current] = 0;
						visited[y][current - 1] = true;
					}
				}
		else if(dir == 3)
			for(int x = 0; x < n; x++)
				for(int y = n - 2; y > - 1; y--) {
					int current = y;
					while(current <= n - 2 && grid[current + 1][x] == 0) {
						grid[current + 1][x] += grid[current][x];
						grid[current][x] = 0;
						current++;
					}
					if(current <= n - 2 && grid[current][x] == grid[current + 1][x] && !visited[current + 1][x]) {
						grid[current + 1][x] *= 2;
						grid[current][x] = 0;
						visited[current + 1][x] = true;
					}
				}
		else
			for(int y = 0; y < n; y++)
				for(int x = n - 2; x > - 1; x--) {
					int current = x;
					while(current <= n - 2 && grid[y][current + 1] == 0) {
						grid[y][current + 1] += grid[y][current];
						grid[y][current] = 0;
						current++;
					}
					if(current <= n - 2 && grid[y][current] == grid[y][current + 1] && !visited[y][current + 1]) {
						grid[y][current + 1] *= 2;
						grid[y][current] = 0;
						visited[y][current + 1] = true;
					}
				}
	}
	
	static void check() {
		for(int y = 0; y < n; y++)
			for(int x = 0; x < n; x++)
				answer = Math.max(answer, grid[y][x]);
	}
	
	static void search(int cnt) {
		check();
		if(cnt == 5)  // 5번까지 움직였으면 종료
			return;
		
		int[][] backup = new int[n][n];
        for (int i = 0; i < n; i++)
            backup[i] = grid[i].clone(); // grid 상태 저장

		for(int d = 1; d <= 4; d++) {
			move(d);
			search(cnt + 1);
			
			for (int i = 0; i < n; i++)
                grid[i] = backup[i].clone(); // 상태 복구
		}		
	}
	
	static void solve() {
		search(0);
		System.out.println(answer);
	}
}

---