[백준 12100] - 2048(Easy) (JAVA)[골드2]

문제

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

12100번: 2048 (Easy)

 

문제 풀이

알고리즘 자체는 정말 간단하지만 그 내부 구현이 조금은 복잡했던 문제였다.

 

N의 크기가 크지 않고, 이동할 수 있는 방향의 개수가 적어서 충분히 완전탐색으로 풀 수 있을 것이라고 판단을 했다.

하지만 고민은 하나의 배열로 풀 수 있을까였다.

 

퍼즐을 밀고, 해당 탐색을 마친다면 이전의 퍼즐 배열로 돌아와야하는데 하나의 배열을 이용하면 풀 수 없을 것이라고 판단을 했다.

 

그다음 고민은 재귀를 호출하기 전에 퍼즐을 밀고(배열을 변경하고) 재귀를 호출  ~~ 재귀를 탈출한다면 배열을 다시 원래대로 돌려야 했고, 전역변수로 선언이 아닌 재귀 호출의 파라미터로 넘겨주는 방식을 선택했다.

기존 dfs에서 depth값을 호출 시 depth+1로 호출하는것과 동일한 방법이라고 생각하면 편할 것이다.

 

즉 나는

1. N과 방향이 적기 때문에 완전탐색으로 풀었다.
2. 이전의 퍼즐 배열 상태를 기억해야 하기에, 2개의 배열을 사용했다.
3. 배열을 재귀함수의 파라미터로 넘겨줘서 해당 호출 내에서만 유효하게 사용했다.

 

그다음으로는 위, 아래, 왼쪽, 오른쪽으로 퍼즐을 옮겨주고 합치는 것이다.

기본적인 방법은 3중 포문으로 진행된다.

방향이 위와 아래라면 열을 고정하고 행을 옮겨주면서 퍼즐을 당겨줘야 한다.

방향이 왼쪽과 오른쪽이라면 행을 고정하고 열을 옮겨주면서 퍼즐을 당겨줘야 한다.

 

퍼즐을 합치는 과정에서 기억해야 할 것이 2가지 있다.

1. 합쳐지는 우선순위가 퍼즐을 옮겨주는 방향과 일치하다.
2. 두 블록 사이에 블록이 있으면 합칠 수 없다.

위 2가지 사실을 기억하고, 방향에 따라 배열을 당겨주고 비워주면 퍼즐은 쉽게 옮겨줄 수 있다.

 

 

전체 코드

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

public class Main {

	static BufferedReader br;
	static StringTokenizer st;
	static int n;
	static int[][] graph = new int[20][20];
	static int answer = 0;

	public static void main(String[] args) throws IOException {
		input();
		int[][] temp = new int[20][20];
		for (int i = 0; i < n; i++) {
			temp[i] = graph[i].clone();
		}
		solution(0, temp);
		System.out.println(answer);
	}

	public static void input() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}

	}

	public static void solution(int cnt, int[][] ary) {
		if (cnt == 5) { // 재귀 끝
			answer = Math.max(answer, findMax(ary));
			return;
		}
		for (int d = 1; d <= 4; d++) { // 상, 하, 좌, 우
			solution(cnt + 1, moveGraph(d, ary));
		}
	}

	public static int[][] moveGraph(int dir, int[][] ary) {
		int[][] moved = new int[n][n];
		for (int i = 0; i < n; i++) {
			moved[i] = ary[i].clone();
		}
		switch (dir) {
			case 1: {
				up(moved);
				break;
			}
			case 2: {
				down(moved);
				break;
			}
			case 3: {
				left(moved);
				break;
			}
			case 4: {
				right(moved);
				break;
			}
		}
		return moved;
	}

	public static int[][] up(int[][] ary) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) { //위에서 부터 합쳐짐.
				for (int k = j + 1; k < n; k++) {
					if (ary[j][i] == 0) {
						ary[j][i] = ary[k][i]; //위로 땡기고
						ary[k][i] = 0; //땡겨진 칸은 비워줌.
					} else if (ary[j][i] == ary[k][i] & isCorrectRow(j, k, i, ary)) { // 합칠려면 사이에 블럭이 있으면 안됨.
						ary[j][i] *= 2;
						ary[k][i] = 0;
						break;
					}
				}
			}
		}
		return ary;
	}

	public static int[][] down(int[][] ary) {
		for (int i = 0; i < n; i++) {
			for (int j = n - 1; j >= 0; j--) { // 아래에서 부터 합쳐짐.
				for (int k = j - 1; k >= 0; k--) {
					if (ary[j][i] == 0) {
						ary[j][i] = ary[k][i]; // 아래로 땡기고
						ary[k][i] = 0; //땡겨진 칸은 비워줌.
					} else if (ary[j][i] == ary[k][i] && isCorrectRow(k, j, i, ary)) { // 합칠려면 사이에 블럭이 있으면 안됨.
						ary[j][i] *= 2;
						ary[k][i] = 0;
						break;
					}
				}
			}
		}
		return ary;
	}

	public static int[][] left(int[][] ary) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) { // 왼쪽에서 부터 합쳐짐
				for (int k = j + 1; k < n; k++) {
					if (ary[i][j] == 0) {
						ary[i][j] = ary[i][k]; // 왼쪽으로 땡기고
						ary[i][k] = 0; //땡겨진 칸은 비워줌.
					} else if (ary[i][j] == ary[i][k] && isCorrectCol(j, k, i, ary)) { // 합칠려면 사이에 블럭이 있으면 안됨.
						ary[i][j] *= 2;
						ary[i][k] = 0;					
						break;
					}
				}
			}
		}
		return ary;
	}

	public static int[][] right(int[][] ary) {
		for (int i = 0; i < n; i++) {
			for (int j = n - 1; j >= 0; j--) { // 아래에서부터 합쳐짐
				for (int k = j - 1; k >= 0; k--) {
					if (ary[i][j] == 0) {
						ary[i][j] = ary[i][k]; // 아래로 땡기고
						ary[i][k] = 0; //땡겨진 칸은 비워줌.
					} else if (ary[i][j] == ary[i][k] && isCorrectCol(k, j, i, ary)) { // 합칠려면 사이에 블럭이 있으면 안됨.
						ary[i][j] *= 2; 
						ary[i][k] = 0;
						break;
					}
				}
			}
		}
		return ary;
	}

	public static boolean isCorrectRow(int r1, int r2, int c, int[][] ary) {
		for (int i = r1 + 1; i < r2; i++) { // r1~r2 사이에 있는지 확인
			if (ary[i][c] != 0) // 사이에 잇다면 합칠 수 없음.
				return false;
		}
		return true;
	}

	public static boolean isCorrectCol(int c1, int c2, int r, int[][] ary) {
		for (int i = c1 + 1; i < c2; i++) { // c1~c2 사이에 있는지 확인
			if (ary[r][i] != 0) // 사이에 잇다면 합칠 수 없음.
				return false;
		}
		return true;
	}

	public static int findMax(int[][] ary) {
		int m = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				m = Math.max(m, ary[i][j]);
			}
		}
		return m;
	}
}