[BOJ 12100] 2048 (Easy)

문제

• BOJ 12100
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

이 문제는 게임룰이 이해가지 않아서 어떻게 접근해야 할지 막막했던 문제이다.
그래서 한 두번정도 코드를 다시 엎어서 작성했고, 시간도 정~~말 오래 걸렸다.
문제에서 지켜야 할 조건은 다음과 같다.

1. 한번 합친 블록은 또 합칠 수 없다.
2. 이동하려는 쪽의 칸이 먼저 합쳐진다.

블록을 4방향으로 이동시킬 수 있는데 이때, 이동한방향과 반대방향부터 블록이 합쳐지는지 확인해야 한다.

1. 5가지 방향을 고르는 중복순열 함수를 만든다.
2. 1번에서 얻어진 중복순열의 방향대로 블록을 탐색한다.

   2-1. switch문으로 각 방향에 대한 조건식을 세운다.
   2-2. 현재 방향의 반대방향에서부터 시작하면서 합쳐질 가능성이 있는 수(0이 아닌 수)이면 큐에다 넣는다.
   2-3. 만약 큐가 비었을 경우에는 현재 라인이 모두 0이라는 의미이므로 다음 라인을 탐색하기 위해 continue한다.

3. 큐에 넣은 수들을 합치기 위한 conbine()함수를 만든다.

   3-1. 큐에서 하나씩 꺼내서 현재 뽑은 숫자와 큐의 가장 윗값을 비교해 같으면 둘다 result배열에 넣어주고, 다르면 뽑지 말고 현재 숫자만 result에 넣어주는 식으로 하여 큐의 모든 리스트들의 합칠 수 있는 숫자는 합쳐준다.
   3-2. 합쳐신 숫자는 반환한다.

4. 3번에서 받은 숫자리스트를 임시 배열 tmp에 넣어준다. 이떄, 먼저 합쳐져야하는 순서에 유의해서 넣어주어야 한다. 이때, 리스트에서 하나씩 꺼내서 Ans에 최대값을 저장해준다.
5. tmp는 다시 copyArr에 옮겨서 다음 방향일 경우에 상태가 보존되도록 해준다.

여기서, 주의할 점은 아레와 같은 맵이 있다고 가정할때,

2 2 0 2
2 0 0 2

좌측으로 움직일 경우 첫번째 행은 4 2 0 0, 두번째 행은 4 0 0 0이 되어야 한다.
즉, 숫자와 숫자 사이에 0이 존재하더라도 합칠 수 있어야 한다.
따라서 나는 애초에 큐에 넣을 때 0이 아닌 숫자만 넣어서 합치고, 이렇게 합친 리스트를 다시 tmp[][]배열에 넣어줄 때 이미 tmp배열은 0으로 초기화되어있기 때문에 신경쓸 것 없이 차례대로 숫자를 넣어주었다.

방향에 대해 맵을 탐색할 때도 2중for문을 사용했는데, 자세히 보면 상↔하, 좌↔우관계이기 때문에 인덱스를 반대로 수정해주면 된다.

이렇게 풀고 제출한 결과 메모리용량이 생각보다 크게 나와서, 다른 방법으로도 풀어봐야겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static int[][] map;
	static int[] di = { -1, 1, 0, 0 }; // 상하좌우
	static int[] dj = { 0, 0, -1, 1 };
	static int Ans; // 최대 크기

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];

		StringTokenizer st;
		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());
			}
		} // End input

		int[] selected = new int[5]; // 이동순서 저장할 배열

		if (N == 1) Ans = map[0][0];
		else per(0, selected);

		System.out.println(Ans);
	}

	//5가지 방향에 대한 중복순열을 구한다.
	private static void per(int idx, int[] selected) { // 중복순열
		if (idx > 4) {
			go(selected); //이 순열로 게임시작
			return;
		}

		for (int i = 0; i < 5; i++) {
			selected[idx] = i;
			per(idx + 1, selected);
		} // End for문
	}

	//현재 뽑인 순열방향에 따라 블록을 탐색한다.
	private static void go(int[] selected) {
		int[][] copyArr = new int[N][N];//map 대신 사용할 배열
		copyArr(copyArr, map);

		for (int idx = 0; idx < 5; idx++) { // 5번 이동
			int d = selected[idx];

			int[][] tmp = new int[N][N];//현재 이동후 블록값을 저장하기 위한 임시 배열
			Queue<Integer> queue = new LinkedList<>();
			ArrayList<Integer> result = new ArrayList<>();

			switch (d) { // 현재 방향에 따라 블록 탐색
			case 0: // 상
				for (int j = 0; j < N; j++) { //블록 탐색 중 0이 아닌 숫자는 큐에 넣고 합친다.
					for (int i = 0; i < N; i++) if(copyArr[i][j] != 0) queue.add(copyArr[i][j]);

					if(queue.size() == 0) continue; //다음 라인을 탐색하기 위해 continue 사용
					result = combine(queue); // 합치기


					// 합친 숫자 리스트를 tmp에 넣는다.
					int index = 0;
					for (int k = 0; k < result.size(); k++) {
						tmp[index][j] = result.get(k);
						Ans = Math.max(Ans, tmp[index][j]);
						index++;
					}
				}
				break;
			case 1: // 하
				for (int j = 0; j < N; j++) {
					for (int i = N-1; i >= 0; i--) if(copyArr[i][j] != 0) queue.add(copyArr[i][j]);
					
					if(queue.size() == 0) continue;
					result = combine(queue); // 합치기

					// tmp에 넣기
					int index = N - 1;
					for (int k = 0; k <result.size(); k++) {
						tmp[index][j] = result.get(k);
						Ans = Math.max(Ans, tmp[index][j]);
						index--;
					}
				}
				break;
			case 2: // 좌
				for (int i = 0; i < N; i++) {
					for (int j = N - 1; j >= 0; j--) if(copyArr[i][j] != 0) queue.add(copyArr[i][j]);

					if(queue.size() == 0) continue;
					result = combine(queue); // 합치기

					// tmp에 넣기
					int index = 0;
					for (int k = 0; k < result.size(); k++) {
						tmp[i][index] = result.get(k);
						Ans = Math.max(Ans, tmp[i][index]);
						index++;
					}
				}
				break;
			case 3: // 우
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) if(copyArr[i][j] != 0) queue.add(copyArr[i][j]);

					if(queue.size() == 0) continue;
					result = combine(queue); // 합치기
					
					// tmp에 넣기
					int index = N-1;
					for (int k = 0; k<result.size(); k++) {
						tmp[i][index] = result.get(k);
						Ans = Math.max(Ans, tmp[i][index]);
						index--;
					}
				}
				break;
			} 
			copyArr(copyArr, tmp);
		}
	}

	//coayArr에 arr배열값을 복사한다.  
	private static void copyArr(int[][] copyArr, int[][] arr) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				copyArr[i][j] = arr[i][j];
			}
		}
	}

	//큐에 있는 값을 하나씩 꺼내서 합칠 수 있는 숫자는 합친다.
	private static ArrayList<Integer> combine(Queue<Integer> queue) {
		ArrayList<Integer> result = new ArrayList<>();
		
		int value = 0;
		while(!queue.isEmpty()) {
			value = queue.poll();
			if(value == 0) continue;
			if(queue.size()==0) {
				result.add(value);
				break;
			}
			if(value == queue.peek()) {
				result.add(value*2);
				queue.poll();
				continue;
			}
			result.add(value);
		}

		return result;
	}
}