[백준 12100번] 2048 (Easy)

문제번호: https://www.acmicpc.net/problem/12100

 

 

문제의 종류

• 구현
• 시뮬레이션

나의 풀이 과정

최근 IM뱅크 코딩테스트 문제에서 구현 관련 문제가 나왔는데, 코드 길이가 길어지면서 실수가 많아졌고, 해당 문제를 풀지 못하였다. 그래서 당분간은 구현 문제들을 많이 풀어보면서 연습할 예정이고, 내일 현대 오토에버 코딩테스트도 예정되어 있기 때문에 겸사겸사 진행하려고 한다.

문제 상황에 유의하면서 문제풀이를 진행한다.

문제 상황
1. 문제에서 이동하는 방향과는 반대의 방향으로 연산을 진행해야 한다.
2. 먼저 이동할 방향에 대해서 move() 메소드로 이동하고, sum() 메소드를 통해 자신과 근접한 숫자가 같을 경우, 해당 숫자를 합해준다.
3. 이후, 다시 move()함수를 이용하여, 0이 된 자리를 다 땡겨온다.

문제의 출력에서 최대 5번을 이동한다고 하여 얻을 수 있는 가장 큰 블록을 출력한다고 하였다.
따라서 이동방향(상, 하, 좌, 우) 4가지 경우의 수에 대하여 5번이므로 4^5 은 combination() 메소드를 통해 이동 방향을 조합으로 저장하고, 해당 방향에 따라 move(), sum(), move() 순으로 순회해주었다.

해당 이동방향을 모두 마친 뒤에는 블록을 순회하면서 가장 최대 값을 res 변수에 저장하였다.

문제 풀이에 사용한 알고리즘
- 재귀 호출을 활용한 Combination
- 시뮬레이션

 

 

 

다음은 전체 코드이다.

package _250516;

import java.io.*;
import java.util.StringTokenizer;

/**
 *packageName    : _250516
 * fileName       : BOJ_G1_12100_2048_2
 * author         : moongi
 * date           : 5/16/25
 * description    :
 */
public class BOJ_G1_12100_2048_2 {
	static int[] dx = {0, -1, 0, 1, 0};
	static int[] dy = {0, 0, 1, 0, -1};

	static int[][] board;
	static int N, res = 0;
	static int[] visited;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		N = Integer.parseInt(br.readLine());
		board = new int[N][N];
		visited = new int[5];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		combination(0, visited);

		System.out.println(res);

	}

	static int solve(int[][] arr) {
		int max = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(arr[i][j] > max)
					max = arr[i][j];
			}
		}

		return max;
	}

	static void combination(int cnt, int[] visited) {
		if (cnt == 5) {
			int[][] tmp = new int[N][N];

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

			for (int i = 0; i < 5; i++) {
				move(tmp, visited[i]);
				sum(tmp, visited[i]);
				move(tmp, visited[i]);
			}

			int answer = solve(tmp);

			if(answer > res)
				res = answer;

			return;
		}

		for (int d = 1; d <= 4; d++) {
			visited[cnt] = d;
			combination(cnt+1, visited);
		}

	}


	static boolean isValid(int x, int y) {
		if (x < 0 || x >= N || y < 0 || y >= N)
			return false;

		return true;
	}

	static void sum(int[][] arr, int dir) {

		if (dir == 1) {
			// 위
			for (int j = 0; j < N; j++) {
				for (int i = 0; i < N - 1; i++) {

					// 이전 행렬과의 합
					if (arr[i][j] == arr[i + 1][j]) {
						arr[i][j] += arr[i + 1][j];
						arr[i + 1][j] = 0;
						i++;
					}

				}
			}
		} else if (dir == 2) {
			// -> // 2
			for (int i = 0; i < N; i++) {
				for (int j = N - 1; j >= 1; j--) {

					// 이전 행렬과의 합
					if (arr[i][j] == arr[i][j - 1]) {
						arr[i][j] += arr[i][j - 1];
						arr[i][j - 1] = 0;
						j--;
					}

				}
			}
		} else if (dir == 3) {
			// 아래
			for (int j = 0; j < N; j++) {
				for (int i = N - 1; i >= 1; i--) {

					// 이전 행렬과의 합
					if (arr[i][j] == arr[i - 1][j]) {
						arr[i][j] += arr[i - 1][j];
						arr[i - 1][j] = 0;
						i--;
					}

				}
			}
		} else {
			// <- // 4
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N - 1; j++) {

					// 이전 행렬과의 합
					if (arr[i][j] == arr[i][j + 1]) {
						arr[i][j] += arr[i][j + 1];
						arr[i][j + 1] = 0;
						j++;
					}

				}
			}
		}

	}

	/**
	 * 이동
	 * @param dir : 해당하는 방향
	 */
	static void move(int[][] arr, int dir) {

		if (dir == 1) {
			// 위
			for (int j = 0; j < N; j++) {
				for (int i = 0; i < N; i++) {
					int nx = i + dx[dir];
					int ny = j + dy[dir];

					if (!isValid(nx, ny))
						continue;

					if (arr[nx][ny] != 0) continue;

					while (true) {
						nx += dx[dir];
						ny += dy[dir];

						if (!isValid(nx, ny)) break;
						if (arr[nx][ny] != 0) break;
					}

					nx -= dx[dir];
					ny -= dy[dir];

					arr[nx][ny] = arr[i][j];
					arr[i][j] = 0;

				}
			}
		} else if (dir == 2) {

			for (int i = 0; i < N; i++) {
				for (int j = N - 1; j >= 0; j--) {
					int nx = i + dx[dir];
					int ny = j + dy[dir];

					if (!isValid(nx, ny))
						continue;

					if (arr[nx][ny] != 0) continue;

					while (true) {
						nx += dx[dir];
						ny += dy[dir];

						if (!isValid(nx, ny)) break;
						if (arr[nx][ny] != 0) break;
					}

					nx -= dx[dir];
					ny -= dy[dir];

					arr[nx][ny] = arr[i][j];
					arr[i][j] = 0;

				}
			}

		} else if (dir == 3) {
			for (int j = 0; j < N; j++) {
				for (int i = N - 1; i >= 0; i--) {
					int nx = i + dx[dir];
					int ny = j + dy[dir];

					if (!isValid(nx, ny))
						continue;

					if (arr[nx][ny] != 0) continue;

					while (true) {
						nx += dx[dir];
						ny += dy[dir];

						if (!isValid(nx, ny)) break;
						if (arr[nx][ny] != 0) break;
					}

					nx -= dx[dir];
					ny -= dy[dir];

					arr[nx][ny] = arr[i][j];
					arr[i][j] = 0;

				}
			}
		} else {

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					int nx = i + dx[dir];
					int ny = j + dy[dir];

					if (!isValid(nx, ny))
						continue;

					if (arr[nx][ny] != 0) continue;

					while (true) {
						nx += dx[dir];
						ny += dy[dir];

						if (!isValid(nx, ny)) break;
						if (arr[nx][ny] != 0) break;
					}

					nx -= dx[dir];
					ny -= dy[dir];

					arr[nx][ny] = arr[i][j];
					arr[i][j] = 0;

				}
			}
		}
	}
}