[백준] 12100 2048(Easy) - 시뮬레이션(Simulation) + 브루트포스(brute force) JAVA

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

12100번: 2048 (Easy)

코드설명

시뮬레이션(Simulation) + 브루트포스(brute force) 문제입니다.

 

문제에서 주어진대로 모든 경우를 완전탐색하면 됩니다.

문제에서 숫자들을 2048 게임의 원리대로 합치는것은 문제에 주어진대로 구현하면 됩니다.

처음에 4가지 방향을 모두 따로 구현하면서 코드를 줄일 수 있는 방법이 있을까 계속 고민하면서 풀었지만 다른 풀이가 떠오르지 않았습니다.

 

다만, 구현중에서 가장 문제가 있었던 부분은, Map, 즉 2048 의 숫자를 기록해두는 배열을 처음에 전역배열로 설정해두었기에 storeMap값이 다음 simulate 재귀함수가 실행될경우 바뀐값으로 갱신되어 올바르게 완전탐색을 진행하지 못했었습니다.

 

전역배열말고, Node[][] storeMap을 각 simulate함수마다 지역변수로 설정하여 해당 문제를 해결할 수 있습니다.

이런 tempMap은 기본적으로 함수 내에서 하도록 습관을 들여야할 것 같습니다.

전역변수에 둘경우 관리가 어렵고, 모든 함수에서 똑같이 접근하므로 각 함수에서의 배열을 따로 선언하지 못하게됩니다.

//	public static Node[][] storeMap;
//    	storeMap = new Node[N][N];
 
public static void simulate(int level) {
    ...
    ...
    Node[][] storeMap = new Node[N][N];
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            storeMap[i][j] = new Node(map[i][j].num, false);
        }
    }	
    ...
	...
 
}

 

위와 같은 오류를 찾아낸 방법은, 아래의 예시와 과정입니다.

3
16 2 2
2 2 2
2 2 16
 
위의 예시입니다.
 
32가 나오는 과정을 표현해보면,
 
===0====
 16 4 4
 4 2 16
 0 0 0
===1====
 0 16 8
 4 2 16
 0 0 0
===2====
 4 16 8
 0 2 16
 0 0 0
===3====
 4 16 8
 2 16 0
 0 0 0
===4====
 4 32 8
 2 0 0
 0 0 0
 
 답 : 32

 

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	public static int N,M, K;
	public static Node[][] map;
//	public static Node[][] storeMap;
	public static int answer = 0;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = { 0, 0, -1, 1};
    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());
    	map = new Node[N][N];
//    	storeMap = new Node[N][N];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			int a = Integer.parseInt(st.nextToken());
    			map[i][j] = new Node(a, false);
    		}
    	}
    	
//    	mergeMap(0);
//    	print(0);
//    	mergeMap(3);
//    	print(1);
//    	mergeMap(0);
//    	print(2);
//    	mergeMap(2);
//    	print(3);
//    	mergeMap(0);
//    	print(4);
    	simulate(0);
    	System.out.println(answer);
    }
    
    public static void simulate(int level) {
    	//가장 큰 블록값은 매번 검사해도 되지만, 결국 많이 이동한결과가 최대값이므로 매번 하지 않아서 효율성을 개선시키자.
    	if(level == 5) {
    		for(int i=0;i<N;i++) {
    			for(int j=0;j<N;j++) {
    				answer = Math.max(answer, map[i][j].num);
    			}
    		}
    		return ;
    	}
    	
    	Node[][] storeMap = new Node[N][N];
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			storeMap[i][j] = new Node(map[i][j].num, false);
    		}
    	}
    	
    	for(int dir = 0; dir < 4; dir++) {
    		//각 방향으로 이동시키자.
    		//이떄 중요한점은, 한번 이동시키고 난 이후에 merged를 모두 fasel로 초기화 시키고서 작동시켜야한다는것이다.
    		mergeMap(dir);
    		simulate(level + 1);
    		
    		//원상복구.
    		for(int i=0;i<N;i++) {
        		for(int j=0;j<N;j++) {
        			map[i][j].num = storeMap[i][j].num;
        			map[i][j].merged = false;
        		}
        	}
    	}
    	
    }
    
    public static void mergeMap(int dir) {
    	
    	//시작할떄는 합병여부를 false로 선언하고 시작합니다.
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			map[i][j].merged = false;
    		}
    	}
    	
    	//어떤 방향으로 합쳐질떄.
    	//위쪽으로 합쳐진다고 가정해보자.
    	//먼저 해당 부분에 Block이 존재한다면, 이동시킬 방향과 가까운곳부터 블록을 이동시킬 것 이다.
    	//만약 이동시킬 방향에서 BLock을 못찾거나 이미 해당 블록이 merged 된 상태라면 바로 아래 블록에 넣어준다.
    	if(dir == 0) {
    		//블록을 위로 이동시키는 경우.
        	//N가지의 열을 기준으로 모두 실행됩니다.
        	for(int col = 0; col < N; col ++) {
        		
        		//해당 행에서 시작점을 잡아줍니다.
        		for(int row = 1; row < N; row++) {
        			int startNum = map[row][col].num;
        			int nr = row;
        				
        			//row가 시작점이 되고 그 시작점을 기준으로 While문을 통해서 가장 맨위의 값을 찾아나갑니다.
        			while(nr >= 0) {
        				nr = nr + dx[dir];
        				
        				//만약 범위를 벗어난다면, 가장 맨위칸이 이동할 칸이 될 것 입니다.. 
        				if(nr <= -1) {
    						map[row][col].num = 0;
    						map[row][col].merged = false;
    						map[0][col].num = startNum;
    						map[0][col].merged = false;
    						break;
    					}
        				//만약 해당 칸이 비어있다면, 한칸 올라갑니다.
        				//다른 작업은 굳이 진행하지 않아도 됩니다.
        				else if(map[nr][col].num == 0) {
        					
        				}
        				//만약 해당 칸이 현재 숫자와 같고, 아직 합쳐진적도 없다면, 해당 부분에서 합쳐주고 종료할 것 입니다.
        				else if(map[nr][col].num == map[row][col].num && map[nr][col].merged == false) {
        					map[row][col].num = 0;
        					map[row][col].merged = false;
        					map[nr][col].num *= 2;
        					map[nr][col].merged = true;
        					break;
        				}
        				//만약 해당 칸이 현재 숫자와 같은데, 이미 합쳐져있다면, 한칸 내려야합니다.
        				else if(map[nr][col].num == map[row][col].num && map[nr][col].merged == true) {
        					nr -= dx[dir];
        					map[row][col].num = 0;
    						map[row][col].merged = false;
        					map[nr][col].num = startNum;
    						map[nr][col].merged = false;
        					break;
        				}
        				//만약 서로 다른 숫자라면, 
        				else if(map[nr][col].num != map[row][col].num) {
        					nr -= dx[dir];
        					map[row][col].num = 0;
    						map[row][col].merged = false;
        					map[nr][col].num = startNum;
    						map[nr][col].merged = false;
        					break;
        				}
        			}
        			
        		}
        	}
    	}
    	//하
    	else if(dir == 1) {
    		//블록을 위로 이동시키는 경우.
        	//N가지의 열을 기준으로 모두 실행됩니다.
        	for(int col = 0; col < N; col ++) {
        		
        		int startRow = 0;
        		//해당 행에서 시작점을 잡아줍니다.
        		for(int row = N-2; row >= 0; row--) {
        			startRow = row;
        			int startNum = map[startRow][col].num;
        			int nr = row;
        				
        			//row가 시작점이 되고 그 시작점을 기준으로 While문을 통해서 가장 맨위의 값을 찾아나갑니다.
        			while(nr <= N) {
        				nr = nr + dx[dir];
        				
        				//만약 범위를 벗어난다면, 가장 맨위칸이 이동할 칸이 될 것 입니다.. 
        				if(nr >= N) {
    						map[startRow][col].num = 0;
    						map[startRow][col].merged = false;
    						map[N-1][col].num = startNum;
    						map[N-1][col].merged = false;
    						break;
    					}
        				//만약 해당 칸이 비어있다면, 한칸 올라갑니다.
        				//다른 작업은 굳이 진행하지 않아도 됩니다.
        				else if(map[nr][col].num == 0) {
        					
        				}
        				//만약 해당 칸이 현재 숫자와 같고, 아직 합쳐진적도 없다면, 해당 부분에서 합쳐주고 종료할 것 입니다.
        				else if(map[nr][col].num == map[startRow][col].num && map[nr][col].merged == false) {
        					map[startRow][col].num = 0;
        					map[startRow][col].merged = false;
        					map[nr][col].num *= 2;
        					map[nr][col].merged = true;
        					break;
        				}
        				//만약 해당 칸이 현재 숫자와 같은데, 이미 합쳐져있다면, 한칸 내려야합니다.
        				else if(map[nr][col].num == map[startRow][col].num && map[nr][col].merged == true) {
        					nr -= dx[dir];
        					map[startRow][col].num = 0;
    						map[startRow][col].merged = false;
        					map[nr][col].num = startNum;
    						map[nr][col].merged = false;
        					break;
        				}
        				//만약 서로 다른 숫자라면, 
        				else if(map[nr][col].num != map[startRow][col].num) {
        					nr -= dx[dir];
        					map[startRow][col].num = 0;
    						map[startRow][col].merged = false;
        					map[nr][col].num = startNum;
    						map[nr][col].merged = false;
        					break;
        				}
        			}
        			
        		}
        	}
    	}
    	
    	//좌 : dir : 2
    	else if(dir == 2) {
    		//블록을 위로 이동시키는 경우.
        	//N가지의 열을 기준으로 모두 실행됩니다.
        	for(int row = 0; row < N; row ++) {
        		
        		//해당 행에서 시작점을 잡아줍니다.
        		for(int col = 1; col < N; col++) {
        			int startNum = map[row][col].num;
        			int nc = col;
        				
        			//row가 시작점이 되고 그 시작점을 기준으로 While문을 통해서 가장 맨위의 값을 찾아나갑니다.
        			while(nc >= 0) {
        				nc = nc + dy[dir];
        				
        				//만약 범위를 벗어난다면, 가장 맨위칸이 이동할 칸이 될 것 입니다.. 
        				if(nc == -1) {
    						map[row][col].num = 0;
    						map[row][col].merged = false;
    						map[row][0].num = startNum;
    						map[row][0].merged = false;
    						break;
    					}
        				//만약 해당 칸이 비어있다면, 한칸 올라갑니다.
        				//다른 작업은 굳이 진행하지 않아도 됩니다.
        				else if(map[row][nc].num == 0) {
        					
        				}
        				//만약 해당 칸이 현재 숫자와 같고, 아직 합쳐진적도 없다면, 해당 부분에서 합쳐주고 종료할 것 입니다.
        				else if(map[row][nc].num == map[row][col].num && map[row][nc].merged == false) {
        					map[row][col].num = 0;
    						map[row][col].merged = false;
        					map[row][nc].num *= 2;
        					map[row][nc].merged = true;
        					break;
        				}
        				//만약 해당 칸이 현재 숫자와 같은데, 이미 합쳐져있다면, 한칸 내려야합니다.
        				else if(map[row][nc].num == map[row][col].num && map[row][nc].merged == true) {
        					nc -= dy[dir];
        					map[row][col].num = 0;
    						map[row][col].merged = false;
        					map[row][nc].num = startNum;
        					map[row][nc].merged = false;
        					break;
        				}
        				//만약 서로 다른 숫자라면, 
        				else if(map[row][nc].num != map[row][col].num) {
        					nc -= dy[dir];
        					map[row][col].num = 0;
    						map[row][col].merged = false;
        					map[row][nc].num = startNum;
    						map[row][nc].merged = false;
        					break;
        				}
        			}
        			
        		}
        	}
    	}
    	//우 : dir : 3
    	else if(dir == 3) {
    		//블록을 위로 이동시키는 경우.
        	//N가지의 열을 기준으로 모두 실행됩니다.
        	for(int row = 0; row < N; row ++) {
        		
        		//해당 행에서 시작점을 잡아줍니다.
        		for(int col = N-2; col >= 0; col--) {
        			int startNum = map[row][col].num;
        			int nc = col;
        				
        			//row가 시작점이 되고 그 시작점을 기준으로 While문을 통해서 가장 맨위의 값을 찾아나갑니다.
        			while(nc <= N) {
        				nc = nc + dy[dir];
        				
        				//만약 범위를 벗어난다면, 가장 맨위칸이 이동할 칸이 될 것 입니다.. 
        				if(nc == N) {
    						map[row][col].num = 0;
    						map[row][col].merged = false;
    						map[row][N-1].num = startNum;
    						map[row][N-1].merged = false;
    						break;
    					}
        				//만약 해당 칸이 비어있다면, 한칸 올라갑니다.
        				//다른 작업은 굳이 진행하지 않아도 됩니다.
        				else if(map[row][nc].num == 0) {
        					
        				}
        				//만약 해당 칸이 현재 숫자와 같고, 아직 합쳐진적도 없다면, 해당 부분에서 합쳐주고 종료할 것 입니다.
        				else if(map[row][nc].num == map[row][col].num && map[row][nc].merged == false) {
        					map[row][col].num = 0;
    						map[row][col].merged = false;
        					map[row][nc].num *= 2;
        					map[row][nc].merged = true;
        					break;
        				}
        				//만약 해당 칸이 현재 숫자와 같은데, 이미 합쳐져있다면, 한칸 내려야합니다.
        				else if(map[row][nc].num == map[row][col].num && map[row][nc].merged == true) {
        					nc -= dy[dir];
        					map[row][col].num = 0;
    						map[row][col].merged = false;
        					map[row][nc].num = startNum;
        					map[row][nc].merged = false;
        					break;
        				}
        				//만약 서로 다른 숫자라면, 
        				else if(map[row][nc].num != map[row][col].num) {
        					nc -= dy[dir];
        					map[row][col].num = 0;
    						map[row][col].merged = false;
        					map[row][nc].num = startNum;
    						map[row][nc].merged = false;
        					break;
        				}
        			}
        			
        		}
        	}
    	}
    	
    }
    
    public static void print(int level) {
    	System.out.println("==="+level+"====");
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			System.out.print(" "+map[i][j].num);
    		}
    		System.out.println();
    	}
    }
    
}
 
class Node{
	int num;
	boolean merged = false;
	public Node(int num, boolean merged) {
		this.num = num;
		this.merged = merged;
	}
}