[backjoon]12100 2048(easy) java

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

12100번: 2048 (Easy)

백준의 삼성 문제들은 배열을 잘 다루면 비교적 쉽게 풀리는 문제다.

이것도 골드2지만

배열을 잘 다룬다면 ㅠㅠ 쉽게 풀수 있지 않을까 생각한다.

1. 상하좌우를 5가지의 중복순열로 만든다.

2. 경우의 수에 맞게 보드를 조합한다.

주의 : 처음 지도의 값은 변하면 안 되므로 복사해서 사용해야하는데 배열의 주소 값이 아닌 실제 값을 복사하도록 하자!

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

class Main {
	static int N, answer;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		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());
			}
		}

		answer = 0;
		dfs(map, 0);
		System.out.println(answer);
	}

	public static void dfs(int[][] map, int cnt) {
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				max = Math.max(map[i][j], max);

			}
		}
		answer = Math.max(max, answer);

		if (cnt == 5)
			return;

		for (int i = 0; i < 4; i++) {
			int[][] tempMap = new int[N][N];
			for (int j = 0; j < N; j++)
				tempMap[j] = map[j].clone();
			move(tempMap, i);
			dfs(tempMap, cnt + 1);
		}
	}

	public static void move(int[][] map, int dir) {
		boolean[][] marked = new boolean[N][N];
		if (dir == 0) {
			for (int r = 0; r < N; r++) {
				for (int c = 0; c < N; c++) {
					int nextR = r;
					while (nextR > 0 && map[nextR - 1][c] == 0)
						nextR--;

					if (nextR > 0 && !marked[nextR - 1][c] && map[nextR - 1][c] == map[r][c]) {
						marked[nextR - 1][c] = true;
						map[r][c] = 0;
						map[nextR - 1][c] *= 2;
					} else {
						// 제일 마지막 일 수도 있고, 단순 올리기일 수도 있음.
						int temp = map[r][c];
						map[r][c] = 0;
						map[nextR][c] = temp;
					}
				}
			}
		} else if (dir == 1) {
			for (int r = N - 1; r >= 0; r--) {
				for (int c = 0; c < N; c++) {
					int nextR = r;
					while (nextR < N - 1 && map[nextR + 1][c] == 0)
						nextR++;
					if (nextR + 1 < N && !marked[nextR + 1][c] && map[nextR + 1][c] == map[r][c]) {
						map[nextR + 1][c] *= 2;
						marked[nextR + 1][c] = true;
						map[r][c] = 0;
					} else {
						int temp = map[r][c];
						map[r][c] = 0;
						map[nextR][c] = temp;
					}
				}
			}
		} else if (dir == 2) {
			for (int c = 0; c < N; c++) {
				for (int r = 0; r < N; r++) {
					int nextC = c;
					while (nextC > 0 && map[r][nextC - 1] == 0)
						nextC--;
					if (nextC > 0 && !marked[r][nextC - 1] && map[r][nextC - 1] == map[r][c]) {
						marked[r][nextC - 1] = true;
						map[r][c] = 0;
						map[r][nextC - 1] *= 2;
					} else {
						int temp = map[r][c];
						map[r][c] = 0;
						map[r][nextC] = temp;
					}
				}

			}
		} else if (dir == 3) {
			for (int c = N - 1; c >= 0; c--) {
				for (int r = 0; r < N; r++) {
					int nextC = c;
					while (nextC < N - 1 && map[r][nextC + 1] == 0)
						nextC++;
					if (nextC < N - 1 && !marked[r][nextC + 1] && map[r][nextC + 1] == map[r][c]) {
						marked[r][nextC + 1] = true;
						map[r][nextC + 1] *= 2;
						map[r][c] = 0;
					} else {
						int temp = map[r][c];
						map[r][c] = 0;
						map[r][nextC] = temp;
					}
				}
			}
		}
	}
}

 

SWEA 재밌는 오셀로가 비슷한 문제인 것 같다.