[Java] 백준12100번 : 2048(Easy)

1. 문제

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

12100번: 2048 (Easy)

 

 

 

2. 풀이 과정

처음엔 쉬운 풀이 방법이 있을까 생각하다가, 안 떠올라서 그냥 모든 경우의 수를 다 돌려보고 생각해봐야겠다 하고 구현했는데, 통과가 되었다.

 

위로, 아래로, 왼쪽으로, 오른쪽으로 각각 0, 1, 2, 3으로 생각하고 5개를 뽑는 중복 순열을 만들었다. 선택한 차례대로 함수를 실행시켜 결과를 냈다.

 

 

1) 최대값 구하기

- 처음 값을 입력받을 때, 확인

- 두 값이 같아서 합칠 때, 확인

=> 두 경우만 고려하면 된다.

 

 

2) 네 방향 중 하나로 이동시키기

- 자신이 앞으로 갈 수 있는 위치 = prev

- 지금 보고 있는 위치 = j

 

 

 

 

단계 1) Up, Down, Left, Right를 따로 생성

 

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

public class Boj12100 {
	static int N, max;
	static int order[], origin[][];
	public static void permutation(int cnt) {
		if(cnt==5) {
			//배열 복사
			int[][] carr = new int[N][N];
			for(int i=0;i<N;i++)
				carr[i] = origin[i].clone();
			
			for(int i=0;i<5;i++) {
				switch(order[i]) {
				case 0:
					goUp(carr);
					break;
				case 1:
					goDown(carr);
					break;
				case 2:
					goLeft(carr);
					break;
				case 3:
					goRight(carr);
					break;
				}
			}
			
			return;
		}
		for(int i=0;i<4;i++) {//4방향 up, down, left, right
			order[cnt]=i;
			permutation(cnt+1);
		}
	}
	
	public static void goUp(int arr[][]) {
		for(int i=0;i<N;i++) {
			int prev = 0;
			for(int j=1;j<N;j++) {
				if(arr[j][i]==0) {
					continue;
				}
				else {
					if(arr[prev][i]==0) {
						arr[prev][i] = arr[j][i];
						arr[j][i] = 0;
					}
					else {
						if(arr[prev][i] == arr[j][i]) {//값이 같으면
							arr[prev][i]*=2;
							arr[j][i] = 0;
							max = Math.max(max, arr[prev][i]);
							prev++;
						}
						else {
							if(++prev != j) {
								arr[prev][i] = arr[j][i];
								arr[j][i] = 0;
							}
						}
					}
				}
			}
		}
	}
	
	public static void goDown(int arr[][]) {
		for(int i=0;i<N;i++) {
			int prev = N-1;
			for(int j=N-2;j>=0;j--) {
				if(arr[j][i]==0) {
					continue;
				}
				else {
					if(arr[prev][i]==0) {
						arr[prev][i] = arr[j][i];
						arr[j][i] = 0;
					}
					else {
						if(arr[prev][i] == arr[j][i]) {//값이 같으면
							arr[prev][i]*=2;
							arr[j][i] = 0;
							max = Math.max(max, arr[prev][i]);
							prev--;
						}
						else {
							if(--prev != j) {
								arr[prev][i] = arr[j][i];
								arr[j][i] = 0;
							}
						}
					}
				}
			}
		}
	}
	
	public static void goLeft(int arr[][]) {
		for(int i=0;i<N;i++) {
			int prev = 0;
			for(int j=1;j<N;j++) {
				if(arr[i][j]==0) {
					continue;
				}
				else {
					if(arr[i][prev]==0) {
						arr[i][prev] = arr[i][j];
						arr[i][j] = 0;
					}
					else {
						if(arr[i][prev] == arr[i][j]) {//값이 같으면
							arr[i][prev]*=2;
							arr[i][j] = 0;
							max = Math.max(max, arr[i][prev]);
							prev++;
						}
						else {
							if(++prev != j) {
								arr[i][prev] = arr[i][j];
								arr[i][j] = 0;
							}
						}
					}
				}
			}
		}
	}
	
	public static void goRight(int arr[][]) {
		for(int i=0;i<N;i++) {
			int prev = N-1;
			for(int j=N-2;j>=0;j--) {
				if(arr[i][j]==0) {
					continue;
				}
				else {
					if(arr[i][prev]==0) {
						arr[i][prev] = arr[i][j];
						arr[i][j] = 0;
					}
					else {
						if(arr[i][prev] == arr[i][j]) {//값이 같으면
							arr[i][prev]*=2;
							arr[i][j] = 0;
							max = Math.max(max, arr[i][prev]);
							prev--;
						}
						else {
							if(--prev != j) {
								arr[i][prev] = arr[i][j];
								arr[i][j] = 0;
							}
						}
					}
				}
			}
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		origin = new int[N][N];
		order = new int[5];//방향 5개 선택
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				origin[i][j] = Integer.parseInt(st.nextToken());
				max = Math.max(max, origin[i][j]);
			}	
		}
		permutation(0);
		System.out.println(max);
	}
}

 

 

 

 

단계 2) Up&Down과 Left&Right를 하나로 묶음

 

묶은 기준은 2차원 배열의 접근 방식이다 Up&Down은 모두 arr[i][j]로 한 열씩 탐색한다면,

Left&Right은 arr[j][i]로 한 행씩 차례로 탐색한다.

 

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

public class Boj12100_2 {
	static int N, max;
	static int order[], origin[][];
	public static void permutation(int cnt) {
		if(cnt==5) {
			//배열 복사
			int[][] carr = new int[N][N];
			for(int i=0;i<N;i++)
				carr[i] = origin[i].clone();
			
			for(int i=0;i<5;i++) 
				move(order[i], carr);
				
			return;
		}
		for(int i=0;i<4;i++) {//4방향 up, down, left, right
			order[cnt]=i;
			permutation(cnt+1);
		}
	}
	
	public static void move(int n, int arr[][]) {
		//up, down, left, right
		int start = (n%2==0) ? 0 : N-1;
		int inc = (n%2==0) ? 1 : -1;
		
		if(n<2) {//up & down
			for(int i=0;i<N;i++) {
				int prev = start;
				for(int j=start+inc; 0<=j && j<N; j+=inc) {
					if(arr[j][i]==0) {
						continue;
					}
					else {
						if(arr[prev][i]==0) {
							arr[prev][i] = arr[j][i];
							arr[j][i] = 0;
						}
						else {
							if(arr[prev][i] == arr[j][i]) {//값이 같으면
								arr[prev][i]*=2;
								arr[j][i] = 0;
								max = Math.max(max, arr[prev][i]);
								prev+=inc;
							}
							else {
								prev+=inc;
								if(prev != j) {
									arr[prev][i] = arr[j][i];
									arr[j][i] = 0;
								}
							}
						}
					}
				}
			}
		}
		else {//left & right
			for(int i=0;i<N;i++) {
				int prev = start;
				for(int j=start+inc; 0<=j && j<N; j+=inc) {
					if(arr[i][j]==0) {
						continue;
					}
					else {
						if(arr[i][prev]==0) {
							arr[i][prev] = arr[i][j];
							arr[i][j] = 0;
						}
						else {
							if(arr[i][prev] == arr[i][j]) {//값이 같으면
								arr[i][prev]*=2;
								arr[i][j] = 0;
								max = Math.max(max, arr[i][prev]);
								prev+=inc;
							}
							else {
								prev += inc;
								if(prev != j) {
									arr[i][prev] = arr[i][j];
									arr[i][j] = 0;
								}
							}
						}
					}
				}
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		origin = new int[N][N];//벽세움
		order = new int[5];//방향 5개 선택
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				origin[i][j] = Integer.parseInt(st.nextToken());
				max = Math.max(max, origin[i][j]);
			}	
		}
		permutation(0);
		System.out.println(max);
	}
}