[JAVA] 백준 - 2048(Easy)

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

12100번: 2048 (Easy)

대학교 1학년때 자주하던 2048 게임이 나왔다!

워낙 자주하던 게임이라 따로 해보지 않아도 규칙을 알고 있었다

※ 게임 해보기 : https://play2048.co/

블록은 상하좌우 네 방향으로 밀 수 있으며, 같은 숫자를 가진 두 블록이 충돌하면 두 값이 합쳐진 하나의 블록으로 변하게 된다

여기서 Stack을 사용해야겠다고 생각했다..!

보드의 크기는 NXN(N=1~20)이고  5번의 이동으로 만들어질 수 있는 가장 큰 수를 구하라고 했는데, 

이동 횟수가 5번으로 제한되고, N의 최댓값이 20으로 별로 크지 않다

따라서 깊이우선탐색(dfs)을 선택하였고, 정확도를 높이기 위해 완전탐색을 진행하였다

 

먼저 초기에 문제 해결을 위해 생각해놓은 절차는 다음과 같다

1. N*N 블럭을 선언한 후, 초기값을 넣어준다 (넣어줄 때, 가장 큰 값을 max의 초기값으로 설정)

2. 블럭 전체를 돌리는 함수(rot)를 정의한다

3. dfs에서 모든 방향을 탐색하기 위해 4번 반복문을 선언하고, 안에 rot와 재귀 호출(dfs) 1번씩 하도록 한다

4. 전역변수 max와 매번 Stack에 쌓이는 값을 비교하여 큰 값을 max에 넣어준다

5. 모든 탐색이 끝난 후 나온 max의 값을 결과값으로 지정해준다

import java.util.Scanner;
import java.util.Stack;

public class Main{
	static int n, max = 0;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		
		int[][] block = new int[n][n];
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				block[i][j]=sc.nextInt();
				if(block[i][j]>max)
					max = block[i][j];
			}
		}
		dfs(0, block);
		System.out.println(max);
	}
	
	//반시계로 회전
	static int[][] rot(int[][] block) {
		int[][] copy = new int[n][n];
		for(int i=0; i<n; i++) {
			System.arraycopy(block[i], 0, copy[i], 0, copy[i].length);
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				block[n-1-j][i]=copy[i][j];
			}
		}
		return block;
	}
	
	static void dfs(int dep, int[][] block) {
		if(dep == 5) return ;
		
		for(int k=0; k<4; k++) {
			int[][] newBlock = new int[n][n];
			Stack<Integer> stack = new Stack<>();
			boolean check = true;
			
			for(int i=0; i<n; i++) {
				for(int j=0;j<n;j++) {
					if(block[i][j]==0) continue;
					if(stack.size()==0) stack.add(block[i][j]);
					else if(stack.peek()==block[i][j] && check) {
							int sum = stack.pop()+block[i][j];
							stack.add(sum);
							check = false;
							if(sum > max) {
								max = sum;
							}
							continue;
					}else stack.add(block[i][j]);
					
					check = true;
				}
				
				int num = stack.size();
				while(!stack.isEmpty()) {
					newBlock[i][--num]= stack.pop();
				}
			}
			dfs(dep+1,newBlock);
			block = rot(block);
		}
	}
}

처음에는 TC 모두 통과했는데도 시작하자마자 "틀렸습니다"가 나왔다...

그래서 질문 게시판 들어가서 모든 반례를 찾아서 입력해보아도 결과값은 정확하게 나왔다

점점 기운이 빠지면서 하기가 싫어졌다가, 다시 한 번 마음을 잡고 코드를 정독해 보았다!

근데 Stack에 쌓인 숫자들을 pop하여 배열에 저장할때, Stack이 LIFO임을 고려하지 않고 대입한게 보였다

//맞는 풀이
	int num = stack.size();
	while(!stack.isEmpty()) {
		newBlock[i][--num]= stack.pop();
	}
                
//틀린 풀이
	int num = 0;
	while(!stack.isEmpty()) {
		newBlock[i][num++]= stack.pop();
	}

그래서 LIFO의 특성을 고려해서 반대로 집어넣어주었다

결과는 성공!

다른 사람들도 다 이렇게 힘들게 사는걸까.. ㅠㅡㅠ 반례만 찾다가 하루종일 걸렸어..

반례도 중요하지만, 지속적인 코드 정독도 중요하다는 것을 ㄲㅐ닫는 순간이었다..★