[ 백준 12100 2048(Easy) ] 문제 풀이(Java) - 삼성 SW역량테스트 기출

백준 2048(Easy) 문제에 대한 풀이를 적어보려고 한다.

 

해당 문제는 solved.ac 기준 난이도 Gold 2에 해당하는데 구현, 브루트 포스 문제다!

(3개월 전에 처음 이 문제 풀었을 때 보고 오늘 다시 한 번 풀어봤는데 쉽게 풀려서 감격,,, 그새 늘었다는 기분이 들어서 뿌듯하다 ><)

 

 

 

문제보기

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

12100번: 2048 (Easy)

나의 풀이

 

최대한 5번 이동시켜 얻을 수 있는 점수의 최대값을 구하는 문제이다. 1번 이동시키는 데 방향 경우의 수가 상, 하, 좌, 우 4개이므로 시간복잡도 O(4^5)에 해당한다.

 

재귀(순열)를 통해서 5번의 이동 방향을 결정해준다음 각 방향에 맞게 블록 이동을 구현해주면 된다.

 

상, 하, 좌, 우 각 방향마다 탐색을 시작하는 for문 인덱스가 다르다. 탐색 순서는 다음과 같다.

아이패드로 끄적끄적,,

 

다음 순서로 탐색을 진행하면서 블록을 0이 아닌 블록을 만날 때까지 이동시켜준 후 바로 인접한 블록과 수가 같으면 합치고 아니면 그냥 두는 방식으로 구현하면 된다.

 

그런데!!

 

합치는 과정에서 "이번 이동 때 이미 합쳐진 블록은 또 다시 합쳐질 수 없다"의 조건이 있으므로 이전에 합쳐졌는지 여부를 체크할 수 있는 배열을 하나 두어 체크해주는 과정이 한 번 더 필요하다!!

 

 

코드

//브루트 포스 문제(재귀 - 순열)

import java.io.*;
import java.util.*;

public class N_12100 {
	static int [][] A;
	static int [] result = new int[5];
	static int totalMax = Integer.MIN_VALUE;
	
	static void go(int index) {
		if(index == 5) {
			int [][] B = new int[A.length][A.length];
			for(int i=0;i<B.length;i++)
				B[i] = A[i].clone();
			
			for(int i=0;i<5;i++) {
				int [][] c = new int[A.length][A.length];    //이전에 합쳐졌는지 여부
				
				if(result[i] == 0) {
					for(int j=0;j<A.length;j++) {
						for(int k=0;k<A.length;k++) {
							//이동
							int nextj = j;
							
							while(true) {
								if(nextj - 1 < 0 || B[nextj - 1][k] != 0) break;
								nextj--;
							}
							
							if(nextj != j) {
								B[nextj][k] = B[j][k];
								B[j][k] = 0;
							}
							
							//합치기
							if(nextj - 1 >= 0 && B[nextj][k] == B[nextj - 1][k] && c[nextj - 1][k] == 0) {
								c[nextj - 1][k] = 1;
								B[nextj - 1][k] *= 2;
								B[nextj][k] = 0;
							}
						}
					}
				}else if(result[i] == 1) {
					for(int j=A.length-1;j>=0;j--) {
						for(int k=0;k<A.length;k++) {
							//이동
							int nextj = j;
							
							while(true) {
								if(nextj + 1 >= A.length || B[nextj + 1][k] != 0) break;
								nextj++;
							}
							
							if(nextj != j) {
								B[nextj][k] = B[j][k];
								B[j][k] = 0;
							}
							
							//합치기
							if(nextj + 1 < A.length && B[nextj][k] == B[nextj + 1][k] && c[nextj + 1][k] == 0) {
								c[nextj + 1][k] = 1;
								B[nextj + 1][k] *= 2;
								B[nextj][k] = 0;
							}
						}
					}
				}else if(result[i] == 2) {
					for(int j=0;j<A.length;j++) {
						for(int k=0;k<A.length;k++) {
							//이동
							int nextk = k;
							
							while(true) {
								if(nextk - 1 < 0 || B[j][nextk - 1] != 0) break;
								nextk--;
							}
							
							if(nextk != k) {
								B[j][nextk] = B[j][k];
								B[j][k] = 0;
							}
							
							//합치기
							if(nextk - 1 >= 0 && B[j][nextk] == B[j][nextk - 1] && c[j][nextk - 1] == 0) {
								c[j][nextk - 1] = 1;
								B[j][nextk - 1] *= 2;
								B[j][nextk] = 0;
							}
						}
					}
				}else if(result[i] == 3) {
					for(int j=0;j<A.length;j++) {
						for(int k=A.length-1;k>=0;k--) {
							//이동
							int nextk = k;
							
							while(true) {
								if(nextk + 1 >= A.length || B[j][nextk + 1] != 0) break;
								nextk++;
							}
							
							if(nextk != k) {
								B[j][nextk] = B[j][k];
								B[j][k] = 0;
							}
							
							//합치기
							if(nextk + 1 < A.length && B[j][nextk] == B[j][nextk + 1] && c[j][nextk + 1] == 0) {
								c[j][nextk + 1] = 1;
								B[j][nextk + 1] *= 2;
								B[j][nextk] = 0;
							}
						}
					}
				}
			}
			
			//최대 수 찾기
			int max = Integer.MIN_VALUE;
			for(int i=0;i<A.length;i++) {
				for(int j=0;j<A.length;j++) {
					if(max < B[i][j])
						max = B[i][j];
				}
			}
			
			if(totalMax < max)
				totalMax = max;
			
			return;
		}
		for(int i=0;i<=3;i++) {     //0: 상, 1: 하, 2:좌, 3: 우
			result[index] = i;
			go(index+1);
			result[index] = 0;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		try {
			int N = Integer.parseInt(br.readLine());
			
			A = new int[N][N];
			
			for(int i=0;i<N;i++) {
				String [] arr = br.readLine().split(" ");
				
				for(int j=0;j<N;j++) {
					A[i][j] = Integer.parseInt(arr[j]);
				}
			}
			
			go(0);
			System.out.println(totalMax);
		}catch(IOException e) {
			e.printStackTrace();
		}
	}

}

 

결과

 

백준 채점결과 pass!