[JAVA] 백준 12100번 : 2048 (Easy) (삼성 SW 역량 테스트 기출 문제)

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

12100번: 2048 (Easy)

문제

쉬운듯 안쉬운듯... 처음 풀기엔 어려웠다... 다른사람의 풀이를 많이 참고함

 

해결 방안

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록값을 구하는 문제로써 5의 깊이를 가지는 DFS를 이용하여 문제를 풀어야겠다고 생각하였다.

1-1. 일단 기저사례에 도달하였을 때 해당 board의 가장 큰 값을 구하고
그 값과 지금까지 깊이가 5가 됬을 때 board의 가장 큰 값의 max 값을 비교한다.

1-2. DFS 탐색 부분은
상하좌우 모든 방면으로 이동시켜준다. 이때 board를 가지고 값들을 이동(merge()시켜주고 전의 값들을 copyBoard에 저장해둬서 반환 했을때 다시 board에 copyBoard 값을 저장해준다.

2. merge() 하는 부분은 Queue 자료구조를 이용하였다. 세로, 가로를 구분하여 한 줄 씩 해결하였다.
Queue 에 한 줄의 값중 0이 아닌 숫자들을 다 넣어준 다음
Queue에 있는 값들을 꺼내가면서 조건 3가지에 따라 board에 Queue에서 빼준 값을 다시 넣어주었다.

코드

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

// 2048 (Easy)
// 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력
public class Main {

	static int n; //(1~20)
	static int[][] board; //게임판
	static int result; // 가장 큰 블록
	
	public static void main(String[] args) throws IOException {
		
		// 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		board = new int[n][n];
		
		String str;
		StringTokenizer st;
		for(int i=0; i<n; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			
			for(int j=0; j<n; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		result = 0;
		dfs(0);
		
		System.out.println(result);

	}
	
	static void dfs(int depth) {
		if(depth>=5) {
			// 게임 판 가장 큰 블록 찾기
			int max = getMaxValue();
			// 최대값 찾아서 비교
			result = Math.max(result, max);
			return;
		}
		else {
			// 복사
			int[][] copyBoard = new int[n][n];
			copyBoard(copyBoard, board);
			
			for(int i=1; i<=4; i++) {
				merge(i);
				dfs(depth+1);
				copyBoard(board, copyBoard);
				
			}
		}
	}
	
	static void copyBoard(int[][] a, int[][] b) {
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				a[i][j] = b[i][j];
			}
		}
	}
	
	// 게임판에서 가장 큰 값 찾기
	static int getMaxValue() {
		int max = 0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				max = Math.max(max, board[i][j]);
			}
		}
		
		return max;
	}
	
	// 
	static void merge(int dir) {
		
		Queue<Integer> q = new LinkedList<>();
		
		switch(dir) {
			// 상
			case 1:
				for(int i=0; i<n; i++) {
					// 세로 한줄 씩 해결
					for(int j=0; j<n; j++) {
						// 0이 아닌 경우 q에 넣어주고
						if(board[j][i]!=0) q.offer(board[j][i]);
						board[j][i] = 0;
					}
					
					// q에는 세로줄이 다 넣어진 상태
					// q에서 꺼내면서 합쳐줄껀 합쳐주고 board에 저장
					int index = 0;
					int popData;
					while(!q.isEmpty()) {
						popData = q.poll();
						
						// 0일 때 (아무것도 안들어간 상태)
						if(board[index][i] == 0) {
							board[index][i] = popData;
						}
						// 같을 때
						else if(board[index][i] == popData) {
							board[index][i] = popData*2;
							index++;
						}
						// 들어가있을 때 (다음거에 데이터 넣어줌)
						else {
							index++;
							board[index][i] = popData;
						}
					}
				}
				break;
				
			// 하
			case 2:
				for(int i=0; i<n; i++) {
					// 세로 한줄 씩 해결(밑줄부터)
					for(int j=n-1; j>=0; j--) {
						// 0이 아닌 경우 q에 넣어주고
						if(board[j][i]!=0) q.offer(board[j][i]);
						board[j][i] = 0;
					}
					
					// q에는 세로줄이 다 넣어진 상태
					// q에서 꺼내면서 합쳐줄껀 합쳐주고 board에 저장
					int index = n-1;
					int popData;
					while(!q.isEmpty()) {
						popData = q.poll();
						
						// 0일 때 (아무것도 안들어간 상태)
						if(board[index][i] == 0) {
							board[index][i] = popData;
						}
						// 같을 때
						else if(board[index][i] == popData) {
							board[index][i] = popData*2;
							index--;
						}
						// 들어가있을 때 (다음거에 데이터 넣어줌)
						else {
							index--;
							board[index][i] = popData;
						}
					}
				}
				break;
				
			// 좌
			case 3:
				for(int i=0; i<n; i++) {
					// 가로 한줄 씩 해결
					for(int j=n-1; j>=0; j--) {
						// 0이 아닌 경우 q에 넣어주고
						if(board[i][j]!=0) q.offer(board[i][j]);
						board[i][j] = 0;
					}
					
					// q에는 가로줄이 다 넣어진 상태
					// q에서 꺼내면서 합쳐줄껀 합쳐주고 board에 저장
					int index = n-1;
					int popData;
					while(!q.isEmpty()) {
						popData = q.poll();
						
						// 0일 때 (아무것도 안들어간 상태)
						if(board[i][index] == 0) {
							board[i][index] = popData;
						}
						// 같을 때
						else if(board[i][index] == popData) {
							board[i][index] = popData*2;
							index--;
						}
						// 들어가있을 때 (다음거에 데이터 넣어줌)
						else {
							index--;
							board[i][index] = popData;
						}
					}
				}
				break;
				
			// 우
			case 4:
				for(int i=0; i<n; i++) {
					// 가로 한줄 씩 해결
					for(int j=0; j<n; j++) {
						// 0이 아닌 경우 q에 넣어주고
						if(board[i][j]!=0) q.offer(board[i][j]);
						board[i][j] = 0;
					}
					
					// q에는 가로줄이 다 넣어진 상태
					// q에서 꺼내면서 합쳐줄껀 합쳐주고 board에 저장
					int index = 0;
					int popData;
					while(!q.isEmpty()) {
						popData = q.poll();
						
						// 0일 때 (아무것도 안들어간 상태)
						if(board[i][index] == 0) {
							board[i][index] = popData;
						}
						// 같을 때
						else if(board[i][index] == popData) {
							board[i][index] = popData*2;
							index++;
						}
						// 들어가있을 때 (다음거에 데이터 넣어줌)
						else {
							index++;
							board[i][index] = popData;
						}
					}
				}
				break;
		
		}
	}

}