[BOJ][JAVA] 12100 2048(EASY)

문제

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

12100번: 2048 (Easy)

풀이

처음에 문제를 읽었을 때는 어렵게 느껴졌는데, 순서를 쪼개어 생각하니 해결할 수 있었다. 쪼개어서 생각하는 버릇을 길러야겠다!

0. 최대 5번 움직이기가 가능

  최대 5번을 움직여야하기 때문에 DFS를 이용하여 종료조건을 걸어주었다. 그리고 상하좌우 4개의 케이스를 나누어 다음 턴으로 넘어갈 수 있도록 하였다.

1. 네 방향 움직이기

 2048은 네 방향으로 움직일 수 있다. 네 방향으로 움직여 같은 수를 더해야 하므로, 배열을 한쪽 방향으로 몰아놔야 한다. 방향마다 스택에 넣는 순서를 다르게 하여 0을 제외한 값들을 줄마다 넣었다.

2. 같은 값 더하기

 스택에 들어간 값들을 빼내어 map2에 입력할 때   pop한 값과 peek값이 같으면 하나의 값으로 입력하고, 그렇지 않을 경우는 pop한 값만 입력하였다. 

3. max값 구하기

 map2에 입력할 때 max값을 체크해주었다. 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	static int n;
	static int max=0;
	public static void dfs(int cnt, int[][] map) {
		if(cnt==5) {
			return;
		}
		int[][] map2 = new int[n][n];
		//상
		for(int i=0;i<n;i++) {
			Stack<Integer> s = new Stack<>();
			for(int j=n-1;j>=0;j--) {
				if(map[j][i]==0) continue;
				s.add(map[j][i]);
			}
			int idx = 0;
			while(!s.isEmpty()) {
				int t = s.pop();
				if(s.size()>0 && t==s.peek()) {
					map2[idx][i]=2*t;
					s.pop();
					if(max<2*t) max=2*t; 
				}else {
					map2[idx][i]=t;
					if(max<t) max=t;
				}
				idx++;
			}
		}
		dfs(cnt+1,map2);
		
		//하
		map2 = new int[n][n];
		for(int i=0;i<n;i++) {
			Stack<Integer> s = new Stack<>();
			for(int j=0;j<n;j++) {
				if(map[j][i]==0) continue;
				s.add(map[j][i]);
			}
			int idx = n-1;
			while(!s.isEmpty()) {
				int t = s.pop();
				if(s.size()>0 && t==s.peek()) {
					map2[idx][i]=2*t;
					s.pop();
					if(max<2*t) max=2*t; 
				}else {
					map2[idx][i]=t;
					if(max<t) max=t;
				}
				idx--;
			}
		}
		dfs(cnt+1,map2);
		
		//좌
		map2 = new int[n][n];
		for(int i=0;i<n;i++) {
			Stack<Integer> s = new Stack<>();
			for(int j=n-1;j>=0;j--) {
				if(map[i][j]==0) continue;
				s.add(map[i][j]);
			}
			int idx = 0;
			while(!s.isEmpty()) {
				int t = s.pop();
				if(s.size()>0 && t==s.peek()) {
					map2[i][idx]=2*t;
					s.pop();
					if(max<2*t) max=2*t; 
				}else {
					map2[i][idx]=t;
					if(max<t) max=t;
				}
				idx++;
			}
		}
		dfs(cnt+1,map2);
		
		//우
		map2 = new int[n][n];
		for(int i=0;i<n;i++) {
			Stack<Integer> s = new Stack<>();
			for(int j=0;j<n;j++) {
				if(map[i][j]==0) continue;
				s.add(map[i][j]);
			}
			int idx = n-1;
			while(!s.isEmpty()) {
				int t = s.pop();
				if(s.size()>0 && t==s.peek()) {
					map2[i][idx]=2*t;
					s.pop();
					if(max<2*t) max=2*t; 
				}else {
					map2[i][idx]=t;
					if(max<t) max=t;
				}
				idx--;
			}
		}
		dfs(cnt+1,map2);		
		
	}
	public static void main(String[] args) throws IOException, NumberFormatException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(),"");
		n = Integer.parseInt(st.nextToken());
		int[][] map = new int[n][n];
		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,map);
		System.out.println(max);
	}
}