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

문제

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

생각할 것

• 최대 5번
• 상하좌우 어디든
• 그 결과 가장 큰 블록의 값
• 방향에 따른 이동으로 블록들이 한 방향으로 빈 블록 없이, '0' 없이 붙는다.
• 이때 같은 수의 블록이 만나면 합쳐진다. x 2 두배.
• 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없다.
• 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다

생각할 것! 배열 복사 - 그냥 하면 안 됨

처음에 초기에 주어진 보드의 상태를 2차원 배열에 저장하고 이를 바탕으로 이동과 합치기를 해 결과를 얻었다.

그렇게 되면 초기 값이 수정되기 때문에 이후의 계산에서 이전의 보드 상태를 바탕으로 로직이 수행된다.

그래서 초기 보드의 값을 가지고 있는 int[][] B 배열을 int[][] board 배열에 복사해주었다.

 

그런데! 자바의 배열 복사는 아래와 같이 하면 안 된다.

 

int[] B = new int[n];
int[] board = B;

int[][] B = new int[n][n];
int[][] board = B;

 

자바에서 객체를 복사할 때는 깊은 복사와 얕은 복사가 있다.

 

https://coding-factory.tistory.com/548 [[Java] 자바 배열을 복사하는 다양한 방법 (깊은 복사, 얕은 복사)] 참고

얕은 복사(Shallow Copy) : 복사된 배열이나 원본 배열이 변경될 때 서로 간의 값이 같이 변경된다.

깊은 복사(Deep Copy) : 복사된 배열이나 원본 배열이 변경될 때 서로 간의 값은 바뀌지 않는다.

 

얕은 복사는 단순히 객체의 주소 값만을 복사하는 것이라 실제로 하나의 주소 값을 가지고 있는 것!

B 배열이 바뀌면 board 배열도 바뀌게 됨

 

그래서 깊은 복사를 해서 객체의 실제 값을 새로운 객체인 board에 복사해야 함

근데 또 2차원 배열의 경우 1차원 배열에서 사용하는 깊은 복사 메서드를 사용해도 깊은 복사가 안됨

1. 이중 for문 사용해서 값 넣어주기

for(int i = 0; i < B.length; i++) {
	for(int j = 0; j < B.length; j++) {
    	board[i][j] = B[i][j];
    }
}

2. for문과 System.arraycopy 사용

for(int i = 0; i < B.length; i++) {
	System.arraycopy(B[i], 0, board[i], 0, B.length);
}

 

전체코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	private static int[][] B;
	private static int[][] board;
	private static int max = 0;
	private static int n;
	private static int[] output;
	private static LinkedList<Integer> boardList;
	private static LinkedList<Integer> num;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		n = N;
		B = new int[N][N];
		output = new int[5];

		//초기 보드 블럭 값을 저장 
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < N; j++) {
				B[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		dfs(0);

		bw.write(max + "");	
		bw.flush();
		bw.close();
		br.close();
	}

	//dfs를 통해 상하좌우 모든 경우의 수를 알아봄 
	public static void dfs(int depth) {
		if(depth == 5) { //최대 5번의 결과를 모두 얻은 경우 
			moveBlock();
			return;
		}

		for(int i = 0; i < 4; i++) {
			output[depth] = i;
			dfs(depth+1);
		}
	}

	//블록이 합쳐지기 전 방향에 따라 블록 모아주는 함수
	public static void moveBlock() {
		//블록 이동 결과를 저장하기 위해 초기 보드 배열을 깊은 복사함 
		board = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				board[i][j] = B[i][j];
			}
		}
		
		for(int i = 0; i < output.length; i++) {
			long dir = output[i]; //방향 값 저장 변수 (0 : 상 / 1 : 하 / 2 : 좌 / 3 : 우)

			for(int j = 0; j < n; j++) {
				boardList = new LinkedList<Integer>();
				for(int k = 0; k < n; k++) {
					if(dir == 0 || dir == 1) //위, 왼쪽일 경우 한 행과 열의 블록 값이 왼쪽 방향으로 모아짐 
						boardList.add(board[k][j]);
					else
						boardList.add(board[j][k]); //아래, 오른쪽일 경우 한 행과 열의 블록 값이 오른쪽 방향으로 모아짐 
				}

				for(int k = 0; k < boardList.size(); k++) { //중간의 '0' 빈 블록을 제거하기 위한 과정 
					if(boardList.get(k) == 0) {
						boardList.remove(k);
						k--;
					}
				}

				//이동하며 0을 삭제한 만큼 왼쪽 오른쪽에 0 채워주기 
				if(dir == 0 || dir == 2) {
					while(boardList.size() != n)
						boardList.addLast(0);
				} else {
					while(boardList.size() != n)
						boardList.addFirst(0);
				}

				//board에 이동 완료한 값 넣어주기 
				if(dir == 0 || dir == 1) {
					for(int k = 0; k < n; k++)
						board[k][j] = boardList.get(k);
				} else {
					for(int k = 0; k < n; k++)
						board[j][k] = boardList.get(k);
				}
			}
			//이동한 보드를 바탕으로 합치기 
			mergeBlock(dir);
			
			//최대 5번 모두 블록을 이동하고 합친 후 가장 큰 값을 얻음 
			if(i == output.length-1) {
				getMax();
			}
		}
	}

	public static void mergeBlock(long dir) {
		//한 줄씩 merge해주기 위해 값 가져와서 LinkedList에 저장 
		for(int i = 0; i < n; i++) {
			num = new LinkedList<Integer>();

			for(int j = 0; j < n; j++) {
				if(dir == 0 || dir == 1)
					num.add(board[j][i]);
				else
					num.add(board[i][j]);
			}

			//merge 
			if(dir == 0 || dir == 2) { //위쪽과 왼쪽의 경우 앞부터 합쳐짐 
				for(int k = 0; k < num.size()-1; k++) {
					if(!num.get(k).equals(0) && num.get(k).equals(num.get(k+1))) {
						int val = num.get(k)*2;
						num.remove(k);
						num.remove(k);
						num.add(k, val);
					}
				}
			} else { //아래쪽과 오른쪽의 경우 뒤부터 합쳐짐 
				for(int k = num.size()-1; k > 0; k--) {
					if(!num.get(k).equals(0) && num.get(k).equals(num.get(k-1))) {
						int val = num.get(k)*2;
						num.remove(k);
						num.remove(k-1);
						num.add(k-1, val);
						k--; //삭제해주고 새로운 합쳐진 값을 넣어줬기 때문에 그 다음 인덱스부터 시작하기 위해 -1 
					}
				}
			}	

			//merge 과정에서 줄어든 자리수 맞춰 주기 
			if(dir == 0 || dir == 2) {
				while(num.size() != n)
					num.addLast(0);
			} else {
				while(num.size() != n)
					num.addFirst(0);
			}

			//merge한 값 배열에 넣어주기 
			if(dir == 0 || dir == 1) {
				for(int k = 0; k < n; k++) {
					board[k][i] = num.get(k);
				}
			} else {
				for(int k = 0; k < n; k++) {
					board[i][k] = num.get(k);
				}
			}
		}
	}

	//보드판에서 가장 큰 수의 블록을 찾는 함수 
	public static void getMax() {
		for(int i = 0; i < n; i++) 
			for(int j = 0; j < n; j++) 
				max = Math.max(board[i][j], max);
	}

}

2차원 배열 board 출력 테스트를 위한 코드

//board 출력 함수 
public static void print() {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			System.out.print(board[i][j] + " ");
		}
		System.out.println();
	}
	System.out.println();
}

반례 모음

10
0 0 64 32 32 0 0 0 0 0
0 32 32 64 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0 
64 64 128 0 0 0 0 0 0 0
0 0 64 32 32 0 0 0 0 0
0 32 32 64 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0 
64 64 128 0 0 0 0 0 0 0
128 32 2 4 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0

1024

 

7
2 2 2 2 2 2 2
2 0 2 2 2 2 2
2 0 2 2 2 2 2
2 0 2 2 2 2 2
2 2 2 0 2 2 2 
2 2 2 2 2 2 0
2 2 2 2 2 2 0

32

 

3
4 512 2
512 2 64
4 8 64

1024

 

3
64 2 128
8 0 0
64 2 8

256

 

3
1024 32 512
0 256 128
128 0 0

2048

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%2312100/src/Main.java

KwonMinha/BOJ