[ 백준 ][ 자바 ][ 12100 ] 2048(EASY)

이런 저런 삽질을 많이 겪은 문제

완벽하게 풀수 있다고 자신은 못하겠다

끙끙대다가 다른 사람들의 풀이를 보고 맞춘 문제인데 

이 문제의 중요한점은 2048의 합쳐짐의 룰을 완벽하게 이해만 하면 된다

merge 함수가 제일 핵심 로직이다

원래는 합치고 이동시키고 두개의 함수로 짯었는데 계속 실패하고...(주륵)

다른 사람들 풀이중 0이 아닌것들을 큐에 넣고 

하는게 효율적이란 말을 듣고 그렇게 짜보았다. 

실전에서 이런 생각을 할 수 있어야할텐데...대단...

여튼 상하 좌우를 이동하고 병합할수 있는 로직이 마련되면

dfs로 모든 방향을 탐색하면 된다

dfs가 익숙하지 않아서 맵을 copy 하는게 이해가 안됬었는데

번뜩 이전 상태를 기억을 해야한다는 게 생각낫다.

merge를 진행하면서 전역 배열인 MAP이 변하는데

분기에서 함수가 RETURN 되면 다음 MERGE를 진행해야하는데

이미 움직여버린 MAP을 쓰면 안되니까 

이전 형상을 기억해야한다.

딱 함수를 찍어논다고 생각하니까 이해가 조금 쉬웠다 

직관적으로 이해는 잘 안된다. 조합문제를 좀 풀어봐야할듯싶다.!

package back;

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


public class Main_backjoon_12100_2048다시 {
	static int MAX;
	static int[][] MAP = new int[101][101];
	static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), "");
		N = Integer.parseInt(st.nextToken());
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int idx = 0;
			while(st.hasMoreTokens()) {
				MAP[i][idx]= Integer.parseInt(st.nextToken());
				idx+=1;
			}
		}
		dfs(0);
		System.out.println(MAX);
	}
	public static void dfs(int depth) {
		
		int[][] tempMap = new int[N+1][N+1];
		copy(tempMap, MAP);
		
		if( depth == 5) {
			findMaxNumber();
			return;
		}
		for(int i =0 ; i < 4; i++) {
			merge(i); 
			dfs(depth+1);
			copy(MAP, tempMap);
		}
	}
	
	public static void findMaxNumber() {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(  MAX < MAP[i][j]) {
					MAX = MAP[i][j];
				}
			}
		}
	}
	
	public static void copy(int[][] arr, int[][] arr2) {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				arr[i][j] = arr2[i][j];
			}
		}
		
	}
	public static void merge(int d) {
		Queue q = new LinkedList();
		int[][] newMap = new int[N+1][N+1];
		
		//상인경우 
		if( d == 0 ) {
			for(int x = 0 ; x < N ;	x++) {
				for(int y = 0; y < N; y++) {
					if(MAP[y][x] != 0 ) {
						q.add(MAP[y][x]);
					}
				}	
				int idx = 0;
				while(!q.isEmpty()) {
					int value = q.peek();
					//System.out.println(value);
					if (newMap[idx][x] == 0) {
						newMap[idx][x] = q.poll();

					}else if(newMap[idx][x] == value ) { //머징
						newMap[idx][x] += q.poll();
						idx+=1;
						
					}else { // 0도 아니고 같지도 않을떄 
						idx +=1;
						newMap[idx][x] = q.poll();
					}			
					//printMap(newMap);
				}
			}
		}
		//하인경우
		if( d == 1 ) {

			for(int x = 0 ; x < N ;	x++) {
				for(int y = N-1; y >= 0; y--) {
					if(MAP[y][x] != 0 ) {
						q.add(MAP[y][x]);
					}
				}	
				int idx = N -1;
				while(!q.isEmpty()) {
					int value = q.peek();
					//System.out.println(value);
					if (newMap[idx][x] == 0) {
						newMap[idx][x] = q.poll();

					}else if(newMap[idx][x] == value ) { //머징
						newMap[idx][x] += q.poll();
						idx-=1;
						
					}else { // 0도 아니고 같지도 않을떄 
						idx -=1;
						newMap[idx][x] = q.poll();
					}			
					//printMap(newMap);
				}
			}
		}

		//좌측인경우 
		if( d == 2 ) {
			
			for(int y = 0 ; y < N ;	y++) {
				for(int x = 0; x < N; x++) {
					if(MAP[y][x] != 0 ) {
						q.add(MAP[y][x]);
					}
				}	
				int idx = 0;
				while(!q.isEmpty()) {
					int value = q.peek();
					//System.out.println(value);
					if (newMap[y][idx] == 0) {
						newMap[y][idx] = q.poll();

					}else if(newMap[y][idx] == value ) { //머징
						newMap[y][idx] += q.poll();
						idx+=1;
						
					}else { // 0도 아니고 같지도 않을떄 
						idx +=1;
						newMap[y][idx] = q.poll();
					}		
					//printMap(newMap);
				}
				
			}
		}
		//우측인경우 
		if( d == 3 ) {
		
			for(int y = 0 ; y < N ;	y++) {
				for(int x = N -1; x >= 0; x--) {
					if(MAP[y][x] != 0 ) {
						q.add(MAP[y][x]);
					}
				}	
				int idx = N-1;
				while(!q.isEmpty()) {
					int value = q.peek();
					//System.out.println(value);
					if (newMap[y][idx] == 0) {
						newMap[y][idx] = q.poll();

					}else if(newMap[y][idx] == value ) { //머징
						newMap[y][idx] += q.poll();
						idx-=1;
						
					}else { // 0도 아니고 같지도 않을떄 
						idx -=1;
						newMap[y][idx] = q.poll();
					}			
					//printMap(newMap);
				}
			}
		}
		copy(MAP,newMap);
	}
	public static void printMap(int[][] MAP) {
		for(int i = 0; i < N; i++) {
			for(int j =0; j < N; j++) {
				System.out.print(MAP[i][j] +" ");
			}
			System.out.println();
		}
	}
	public static void printMoveMap(int[][] moveMap) {
		for(int i = 0; i < N; i++) {
			for(int j =0; j < N; j++) {
				System.out.print(moveMap[i][j] +" ");
			}
			System.out.println();
		}
	}

}