[백준BOJ] 12100번 2048(Easy).java

 

백준 저지에서 2048(Easy)를 자바를 통해 풀어 보았다. 

 

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

12100번: 2048 (Easy)

 

12100번 2048(Easy).java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

12100번 2048(Easy)

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

설명

호흡이 정말 긴 문제다. 천천히 하나씩 살펴보자.

 

구현, 시뮬레이션 문제이며 백트래킹을 활용하여 풀 수 있다. 구현 과정이 굉장히 까다롭고 복잡했다.

 

보드를 상하좌우 중 하나를 골라 이동시키는 것이 한 번의 움직임이다. 총 5번을 움직여서 나올 수 있는 값 중 최댓값을 구하는 문제이다. 

 

상하좌우는 (1,0), (-1,0), (0,1), (0,-1)로 구분하였다. 따라서 각 방향에 따라 가로, 세로, 방향에 맞춰 보드에 접근할 수 있어야 했다. 4개의 경우에 맞춰 하드 코딩을 할 수도 있었겠지만 일반화하고 싶었고 이 과정이 오래 걸렸다. 다음은 각 방향에 따라 원하는 라인을 가져오는 반복문이다.

if(di[d]+dj[d]==-1)k=N-1;
for(int x=0;x<N;x++) {//각 줄마다 고려, 방향에 따라 가로줄, 세로줄, 방향이 바뀜
  int[] temp = new int[N];
  //각 줄만 뺴오기
  //한줄씩 이동시키기 위해 방향에 따라 한 줄씩 temp배열에 저장
  for(int y=0;y<N;y++) {
    temp[y] = tempBoard[(y*di[d]+N+x*dj[d]+k)%N][(y*dj[d]+N+x*di[d]+k)%N];
  }
}

예를 들어 (1,0)이라면 위에서 아래로 접근하는게 편할 것이라고 생각했고 세로줄, 아래방향으로 배열을 얻어오고 싶었다. N=3이라면 (0,0),(1,0),(2,0)을 얻어온다. 

 

이렇게 줄 하나를 배열로 가져왔다면 이 배열을 방향에 맞춰 이동시켜야한다. 이동 후에는 0이 아닌 숫자 사이에 0이 삽입되는 경우는 없다. 따라서 0이 아닌 숫자를 일단 몰아 놓았다.

 

다음으로 연속되는 숫자가 있다면 합치고 그렇지 않다면 위치만 이동시켰다. 

//같은 숫자가 연속되면 합치고, 연속되지 않으면 위치만 이동
index=0;//다음 숫자가 위치할 index
  for(int i=0;i<N-1;i++) {
    if(temp2[i]==temp2[i+1]) {//연속된 숫자가 같다면
      temp2[index++]=temp2[i++]*2;//index위치에 2배한 값을 두기 + 뒤에 있는 숫자는 이미 합쳐졌으므로 i++
      temp2[i]=0;//뒤에 있는 숫자는 사라졌으므로 0으로 변환
    }
    else if(temp2[i]!=0){//연속되지 않았다면
      temp2[index++]=temp2[i];//위치만 이동
    }
}

index는 숫자들이 놓여질 위치이다. 앞에서부터 하나씩 채우기 때문에 채울 때마다 1씩 증가시킨다. 같은 숫자가 연속된다면 합치고 index에 놓는다. 이때 연속된 숫자 중 뒤에 있는 숫자는 합쳐졌기 때문에 다시 고려되어선 안 된다. 따라서 반복문의 i를 증가하고 해당 위치를 0으로 초기화한다. 같은 숫자가 연속되지 않는다면 해당 숫자의 위치만 index로 옮긴다.

 

같은 숫자가 연속되는 경우가 많을 수록 index와 배열의 길이 차이는 크다. 따라서 차이만큼 남은 부분은 0으로 채워야한다. 

 

현재 temp2는 이동이 완료된 배열이다. 이 배열을 다시 board에 옮긴다.

for(int y=0;y<N;y++) {//temp2는 이동후 배열임 -> tempBoard에 temp2를 저장
  tempBoard[(y*di[d]+N+x*dj[d]+k)%N][(y*dj[d]+N+x*di[d]+k)%N] = temp2[y];
}

 

이 과정을 백트래킹을 활용하여 5번 반복한다. 이렇게 나온 결과물 중 최댓값을 비교하여 구한다.

 

코드

//12100번 2048(Easy).java
package boj20211215;

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

public class Easy2048_12100 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int answer=0;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		int[][] board = new int[N][N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			for(int j=0;j<N;j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		move(0, board, N);
		System.out.println(answer);
	}
    
    static void move(int count, int[][] board, int N) {
    	//최대 5번 이동
    	if(count==5) {
    		//한 번 합쳐진 블록은 사라지지 않으므로 최댓값은 마지막에만 확인해도 상관없음
    		for(int i=0;i<N;i++) {
        		for(int j=0;j<N;j++) {
        			if(answer < board[i][j]) {
        				answer = board[i][j];
        			}
        		}
        	}
    		return;
    	}
    	
    	//4방향 상하좌우 어디로 이동시킬 것인지
    	int[] di= {1,-1,0,0};
    	int[] dj= {0,0,1,-1};
    	for(int d=0;d<4;d++) {
    		
    		//임시보드로 저장 - 이동 전 보드를 보존하기 위함
    		int[][] tempBoard = new int[N][N];
    		
    		for(int i=0;i<N;i++) {
    			for(int j=0;j<N;j++) {
    				tempBoard[i][j] = board[i][j];
    			}
    		}
    		
    		int k=0;
    		if(di[d]+dj[d]==-1)k=N-1;
    		for(int x=0;x<N;x++) {//각 줄마다 고려, 방향에 따라 가로줄, 세로줄, 방향이 바뀜
    			int[] temp = new int[N];
    			//각 줄만 뺴오기
    			//한줄씩 이동시키기 위해 방향에 따라 한 줄씩 temp배열에 저장
    			for(int y=0;y<N;y++) {
    				temp[y] = tempBoard[(y*di[d]+N+x*dj[d]+k)%N][(y*dj[d]+N+x*di[d]+k)%N];
    			}
    			//각 줄의 이동시키기
    			//이동 후 저장될 temp2 배열
    			int[] temp2=new int[N];
				int index=0;//놓여질 위치
				
				//0을 죄외한 숫자들 한 쪽으로 몰아놓기
				for(int i=0;i<N;i++) {
					if(temp[i]!=0) {
						temp2[index++]=temp[i];
					}
				}
				
				//같은 숫자가 연속되면 합치고, 연속되지 않으면 위치만 이동
				index=0;//다음 숫자가 위치할 index
				for(int i=0;i<N-1;i++) {
					if(temp2[i]==temp2[i+1]) {//연속된 숫자가 같다면
						temp2[index++]=temp2[i++]*2;//index위치에 2배한 값을 두기 + 뒤에 있는 숫자는 이미 합쳐졌으므로 i++
						temp2[i]=0;//뒤에 있는 숫자는 사라졌으므로 0으로 변환
					}
					else if(temp2[i]!=0){//연속되지 않았다면
						temp2[index++]=temp2[i];//위치만 이동
					}
				}
				temp2[index++]=temp2[N-1];//위 반복문에서 고려되지 못한 마지막 배열 위치 조정
				while(index<N) {//나머지는 0으로 채움
					temp2[index++]=0;
				}
    			for(int y=0;y<N;y++) {//temp2는 이동후 배열임 -> tempBoard에 temp2를 저장
    				tempBoard[(y*di[d]+N+x*dj[d]+k)%N][(y*dj[d]+N+x*di[d]+k)%N] = temp2[y];
    			}
    		}
    		//다음 이동으로 진행
    		move(count+1, tempBoard, N);
    	}
    }
    
}