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

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

12100번: 2048 (Easy)

중복순열 + deque + 시뮬레이션 문제

1. 중복순열로 5번 돌렸을 때의 방향을 구한다.

2. 중복순열당 시뮬레이션을 시작한다.

3. deque를 담은 리스트를 선언하고 N개만큼 초기화한다.

4. 가로/세로로 구분해서 저장하고 북쪽/서쪽 방향은 앞에서, 동쪽/남쪽 방향은 뒤에서 넣는다(deque add, push)

5. 큐에 들어 온 값들을 처리한다.
   1 - 0이면 채운다.
   2 - 숫자가 있으면 자신과 비교한다.
   3 - 숫자가 같다면 더한다
   4 - 숫자가 다르다면 반대 방향으로 한칸 이동하여 저장한다.

6. 시뮬레이션이 끝나면 map을 검사해서 최대값을 찾는다.

package Study0307;

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

class Position{
	int row, col,value;
	public Position(int row, int col,int value) {
		this.row = row;
		this.col = col;
		this.value = value;
	}
}
public class 게임2048 {
	public static final int[] dx = {-1,0,1,0};
	public static final int[] dy = {0,1,0,-1};
	public static int N;
	public static int[][] map;
	public static int[][] copyMap;
	public static int[] num = {0,1,2,3};
	public static int[] arr;
	public static Queue<Integer> q;
	public static int max = Integer.MIN_VALUE;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		
		map = new int[N][N];
		copyMap = new int[N][N];
		arr = new int[5];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		permutation(0);
		System.out.println(max);
	}
	public static void permutation(int cnt) {
		if(cnt == 5) {
			q = new LinkedList<>();
			for (int i = 0; i < 5; i++) {
				q.add(arr[i]);
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					copyMap[i][j] = map[i][j];
				}
			}
			go();
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					max = Integer.max(copyMap[i][j] , max);
				}
			}
			return;
		}
		
		for (int i = 0; i < 4; i++) {
			arr[cnt] = num[i];
			permutation(cnt+1);
		}
	}
	public static void go() {
		ArrayList<Deque<Position>> list = new ArrayList<>();
		
		for (int i = 0; i < N; i++) {
			list.add(new LinkedList<>());
		}
		while(!q.isEmpty()) {
			int dir = q.poll();
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					int nx=i,ny=j;
					if(copyMap[i][j] == 0) continue;
					while(true) {
						nx += dx[dir];
						ny += dy[dir];
						
						if(nx<0 || nx >=N || ny<0 || ny>=N) {
							nx -= dx[dir];
							ny -= dy[dir];
							if		 (dir == 0){
								list.get(j).add(new Position(nx,ny,copyMap[i][j]));
							}else if (dir == 1){
								list.get(i).push(new Position(nx,ny,copyMap[i][j]));
							}else if (dir == 2){
								list.get(j).push(new Position(nx,ny,copyMap[i][j]));
							}else if (dir == 3){
								list.get(i).add(new Position(nx,ny,copyMap[i][j]));
							}
							copyMap[i][j] = 0;
							break;
						}
					}
				}
			}
			for (int i = 0; i < N; i++) {
				int cnt = 0;
				while(!list.get(i).isEmpty()) {
					
					Position pos = list.get(i).poll();
					
					int nxq = pos.row + dx[(dir+2)%4]*cnt;
					int nyq = pos.col + dy[(dir+2)%4]*cnt;
					if(copyMap[nxq][nyq] == 0) {
						//map이 0이라면 값을 채운다.
						copyMap[nxq][nyq] = pos.value;
					}else if(copyMap[nxq][nyq] == pos.value){
						//map에 숫자가 있는데 나와 같다면 더하고 cnt를 증가시킨다.
						copyMap[nxq][nyq] += pos.value;
						cnt++;
					}else {
						//map에 숫자가 있는데 나와 다르다면 cnt를 증가시키고 map에 저장한다.
						cnt++;
						nxq = pos.row + dx[(dir+2)%4]*cnt;
						nyq = pos.col + dy[(dir+2)%4]*cnt;
						copyMap[nxq][nyq] = pos.value;
					}	
				}
			}
			
		}
	}
}