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

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

디버깅하는데 정말 하루 꼬박 걸렸던 문제였습니다.

 

문제를 풀면서 테스트의 중요성을 다시금 느꼈습니다. 특히 구현 문제에서는 더욱더.

구현 문제의 경우 알고리즘의 난이도 자체가 높다기보다 복잡도가 올라가면서 나타나는 실수들 때문에 발목을 잡히기 쉽습니다.

적절하게 메서드로 분리하고 메서드마다 테스트를 착실히 하는게 중요하다고 느껴졌습니다.

 

저도 테스트 메서드를 작성하고 나서야 짧은 시간 안에 문제점을 확인할 수 있었습니다. 진작에 이랬다면 시간을 아꼈을텐데..

 

기본적인 방식은 dfs를 이용한 백트래킹과 유사합니다. 재귀함수 호출 전에 이동하고 재귀함수를 호출할때 count를 셉니다. 그리고 재귀함수가 리턴될 때 board를 복구하도록 해줍니다.

 

구현 상의 팁이라면

판의 이동 방향에 따라 row, column 한 줄 단위로 메서드를 구성했고, 수를 합치는 메서드는 방향을 신경쓰지 않아도 되도록  scanXX, updateXX 함수들에 방향을 지정했습니다.

 

 

...

/*
백준 12100번 - 2048(Easy)
https://www.acmicpc.net/problem/12100
 */
public class Main {
	static int n;
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		n = reader.readInt();

		int[][] board = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			for (int j = 0; j < n; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		System.out.println(solve( 0, 0, board));
	}

	private static int solve(int count, int maxVal,int[][] board) {
		if(count == 5) return maxVal;

		int ret = 0;
		//수정하기 전에 복구를 위해 복사
		int[][] copyBoard = new int[n][n];
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				copyBoard[j][k] = board[j][k];
			}
		}

		// 0:상, 1:하, 2:우, 3:좌
		for (int i = 0; i < 4; i++) {
			int max = move(i, board);
			ret = Math.max(solve(count+1, max, board), ret);

			//복구
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					board[j][k] = copyBoard[j][k];
				}
			}
		}
		return ret;
	}
	/*
	방향으로 블록들을 이동
	 */
	public static int move(int direction, int[][] board) {
		int n = board.length;
		int maxVal = 0;
		//위로 이동. 아래로 스캔
		if(direction == 0) {
			for (int col = 0; col < n; col++) {
				List<Integer> line = scanOneColumn(col, true,board);
				List<Integer> newLine = mergeSameNumber(line);
				maxVal = Math.max(updateOneColumn(col,true, newLine, board), maxVal);
			}
		}
		//아래. 위로 스캔
		if(direction == 1) {
			for (int col = 0; col < n; col++) {
				List<Integer> line = scanOneColumn(col, false, board);
				List<Integer> newLine = mergeSameNumber(line);
				maxVal = Math.max(updateOneColumn(col,false, newLine, board), maxVal);
			}
		}
		//우. 왼쪽으로 스캔
		if(direction == 2) {
			for (int row = 0; row < n; row++) {
				List<Integer> line = scanOneRow(row, false, board);
				List<Integer> newLine = mergeSameNumber(line);
				maxVal = Math.max(updateOneRow(row,false, newLine, board), maxVal);
			}
		}
		//좌. 오른쪽으로 스캔
		if(direction == 3) {
			for (int row = 0; row < n; row++) {
				List<Integer> line = scanOneRow(row, true, board);
				List<Integer> newLine = mergeSameNumber(line);
				maxVal = Math.max(updateOneRow(row,true, newLine, board), maxVal);
			}
		}
		return maxVal;
	}

	public static int updateOneRow(int row, boolean isRight, List<Integer> line, int[][] board) {
		int n = board.length;
		int maxVal = 0;
		if(isRight) {
			for (int col = 0; col < n; col++) {
				board[row][col] = line.get(col);
				maxVal = Math.max(maxVal, board[row][col]);
			}
		}else {
			for (int col = 0; col < n; col++) {
				board[row][n-col-1] = line.get(col);
				maxVal = Math.max(maxVal, board[row][n-col-1]);
			}
		}
		return maxVal;
	}

	public static int updateOneColumn(int col, boolean isDown, List<Integer> line, int[][] board) {
		int n = board.length;
		int maxVal = 0;
		if(isDown) {
			for (int row = 0; row < n; row++) {
				board[row][col] = line.get(row);
				maxVal = Math.max(maxVal, board[row][col]);
			}
		}else {
			for (int row = 0; row < n; row++) {
				board[n-row-1][col] = line.get(row);
				maxVal = Math.max(maxVal, board[n-row-1][col]);
			}
		}
		return maxVal;
	}

	public static List<Integer> mergeSameNumber(List<Integer> line) {
		int n = line.size();
		//먼저 빈칸 제거
		line = line.stream().filter(e -> e != 0).collect(Collectors.toList());
		int size = line.size();
		for (int i = 0; i < size; i++) {
			if(i < size-1 && line.get(i).intValue() == line.get(i+1).intValue()) {
				line.set(i, line.get(i)*2);
				line.remove(i+1);
				size = line.size();
			}
		}

		while(line.size() < n) {
			line.add(0);
		}
		return line;
	}

	public static List<Integer> scanOneRow(int row, boolean isRight, int[][] board) {
		int n = board.length;
		List<Integer> l = new ArrayList<>();
		if(isRight) {
			for (int col = 0; col < n; col++) {
				l.add(board[row][col]);
			}
		} else {
			for (int col = n-1; col >= 0; col--) {
				l.add(board[row][col]);
			}
		}
		return l;
	}

	public static List<Integer> scanOneColumn(int col, boolean isDown, int[][] board) {
		int n = board.length;
		List<Integer> l = new ArrayList<>();
		if(isDown) {
			for (int row = 0; row < n; row++) {
				l.add(board[row][col]);
			}
		} else {
			for (int row = n-1; row >= 0; row--) {
				l.add(board[row][col]);
			}
		}
		return l;
	}
}

class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}