백준 12100 [2048 (Easy)] - JAVA

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

12100번: 2048 (Easy)

 

풀이

1. 상하좌우 이동이 5번되었을때 최댓값을 구해야한다.

  - 상하좌우 이동을 DFS로 구현해야겠구나 생각

  - 재귀함수의 파라미터로 이동횟수를 +1씩해서 전달

  - 재귀함수를 사용할때 배열의 값을 복제하여 파라미터로 넘겨준다.

 

    *중요*

    2차원 배열은 clone 메소드로 단순복사할 수 없다. 별도의 로직 구현이 필요하다. 해당 내용이 궁금하면 여기

 

2. 한번의 이동에서 같은값을 가지는 블록이 충돌하면 값이 합쳐진다. 똑같은 수가 3개있는경우 이동하려는 쪽의 칸이 먼저 합쳐진다.

  - Queue의 FIFO(First In Fisrt Out)의 특성을 이용하여 값을 계산한다.

  - Queue에 넣는 순서는 이동하려는 쪽에 가까운 값부터 넣는다.

  

소스코드

package algorithm.dfs;

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

/**
 * 
 * 2048(Easy)
 *
 */
public class Q12100 {

	static int N;
	static int nMaxVal = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");

		N = Integer.parseInt(input[0]);
		
		int[][] arrMap = new int [N][N];
		for(int nRow = 0 ; nRow < N ; nRow++) {
			input = br.readLine().split(" ");
			for(int nCol = 0 ; nCol < N ; nCol++) {
				arrMap[nRow][nCol] = Integer.parseInt(input[nCol]);
			}
		}
		
		for(int nBse = 0 ; nBse < 4 ; nBse++) {
			dfs(nBse, getClone(arrMap),1);
		}
		System.out.println(nMaxVal);
	}


	private static void dfs(int nBse, int[][] arrMap, int cnt) {
		//큐의 FIFO 특성을 이용해서 두개의 값을 비교한다.
		Queue<Integer> q = new LinkedList<Integer>();
		
		//0:좌, 1:우, 2:상, 3:하
		switch(nBse) {
			//0:좌
			case 0 :
				for(int nRow = 0; nRow < N ; nRow++) {
					for(int nCol = 0 ; nCol < N ; nCol++) {
						if(arrMap[nRow][nCol] != 0) {
							q.add(arrMap[nRow][nCol]);
							arrMap[nRow][nCol] = 0;
						}
					}
					
					int nCurCol = 0;
					if(q.size() > 0) {
						arrMap[nRow][nCurCol] = q.poll();
					}
					
					while(!q.isEmpty()) {
						int nTargetVal = q.poll();
						
						if(arrMap[nRow][nCurCol] == nTargetVal) {
							arrMap[nRow][nCurCol] *= 2;
							nCurCol++;
							if(q.size() > 0) {
								arrMap[nRow][nCurCol] = q.poll();
							}
						}else {
							arrMap[nRow][++nCurCol] = nTargetVal;
						}
					}
				}
				break;
			//1:우
			case 1:
				for(int nRow = 0; nRow < N ; nRow++) {
					for(int nCol = N-1 ; nCol >= 0 ; nCol--) {
						if(arrMap[nRow][nCol] != 0) {
							q.add(arrMap[nRow][nCol]);
							arrMap[nRow][nCol] = 0;
						}
					}
					
					int nCurCol = N-1;
					if(q.size() > 0) {
						arrMap[nRow][nCurCol] = q.poll();
					}
					while(!q.isEmpty()) {
						int nTargetVal = q.poll();
						
						if(arrMap[nRow][nCurCol] == nTargetVal) {
							arrMap[nRow][nCurCol] *= 2;
							nCurCol--;
							if(q.size() > 0) {
								arrMap[nRow][nCurCol] = q.poll();
							}
						}else {
							arrMap[nRow][--nCurCol] = nTargetVal;
						}
					}
				}
				break;
			//2:상
			case 2:
				for(int nRow = 0; nRow < N ; nRow++) {
					for(int nCol = 0 ; nCol < N ; nCol++) {
						if(arrMap[nCol][nRow] != 0) {
							q.add(arrMap[nCol][nRow]);
							arrMap[nCol][nRow] = 0;
						}
					}
					
					int nCurCol = 0;
					if(q.size() > 0) {
						arrMap[nCurCol][nRow] = q.poll();
					}
					while(!q.isEmpty()) {
						int nTargetVal = q.poll();
						
						if(arrMap[nCurCol][nRow] == nTargetVal) {
							arrMap[nCurCol][nRow] *= 2;
							nCurCol++;
							if(q.size() > 0) {
								arrMap[nCurCol][nRow] = q.poll();
							}
						}else {
							arrMap[++nCurCol][nRow] = nTargetVal;
						}
					}
				}
				break;
			//3:하
			case 3:
				for(int nRow = 0; nRow < N ; nRow++) {
					for(int nCol = N-1 ; nCol >= 0 ; nCol--) {
						if(arrMap[nCol][nRow] != 0) {
							q.add(arrMap[nCol][nRow]);
							arrMap[nCol][nRow] = 0;
						}
					}
					
					int nCurCol = N-1;
					if(q.size() > 0) {
						arrMap[nCurCol][nRow] = q.poll();
					}
					
					while(!q.isEmpty()) {
						int nTargetVal = q.poll();
						
						if(arrMap[nCurCol][nRow] == nTargetVal) {
							arrMap[nCurCol][nRow] *= 2;
							nCurCol--;
							if(q.size() > 0) {
								arrMap[nCurCol][nRow] = q.poll();
							}
						}else {
							arrMap[--nCurCol][nRow] = nTargetVal;
						}
					}
				}
				break;
		}
		
		//5번 움직였을때 최대값 찾기
		if(cnt == 5) {
			valConfirm(arrMap);
			return;
		}
		
		for(int nIdx = 0 ; nIdx < 4 ; nIdx++) {
			dfs(nIdx, getClone(arrMap),cnt+1);
		}
	}

	//최대값 찾기
	private static void valConfirm(int[][] arrMap) {
		for(int nRow = 0; nRow < N ; nRow++) {
			for(int nCol = 0 ; nCol < N ; nCol++) {
				if(nMaxVal < arrMap[nRow][nCol]) {
					nMaxVal = arrMap[nRow][nCol];
				}
			}
		}
	}


	//2차원배열 복사
	private static int[][] getClone(int[][] arr) {
		
		int[][] arrReturn = new int[N][N];
	    for (int nIdx=0; nIdx<N; nIdx++) {
	    	arrReturn[nIdx] = arr[nIdx].clone();
	    }
	    return arrReturn;
	}
}