문제
테스트케이스
3
2 2 2
4 4 4
8 8 8
output: 16
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main_bj_12100_2048 {
static int N;
static int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static int ans;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[][] map = new int[N][N];
for (int i = 0; i < N; i++) {
String[] row = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(row[j]);
}
}
if (N == 1) {
System.out.println(map[0][0]);
return;
}
ans = 0;
dfs(0, map);
System.out.println(ans);
}
static void dfs(int n, int[][] map) {
if (n == 5) {
int maxResult = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
maxResult = map[i][j] > maxResult ? map[i][j] : maxResult;
}
}
ans = maxResult > ans ? maxResult : ans;
return;
}
for (int d = 0; d < 4; d++) {
int[][] moveMap = moveMap(d, map);
moveMap = mergeMap(d, moveMap);
moveMap = moveMap(d, moveMap);
dfs(n + 1, moveMap);
}
}
static int[][] moveMap(int d, int[][] originMap) {
int[][] moveMap = new int[N][N];
switch (d) {
case 0: // 우
for (int i = 0; i < N; i++) {
int newj = 0;
for (int j = 0; j < N; j++) {
if (originMap[i][j] != 0)
moveMap[i][newj++] = originMap[i][j];
}
}
break;
case 1: // 하
for (int j = 0; j < N; j++) {
int newi = 0;
for (int i = 0; i < N; i++) {
if (originMap[i][j] != 0)
moveMap[newi++][j] = originMap[i][j];
}
}
break;
case 2: // 좌
for (int i = 0; i < N; i++) {
int newj = N - 1;
for (int j = N - 1; j >= 0; j--) {
if (originMap[i][j] != 0)
moveMap[i][newj--] = originMap[i][j];
}
}
break;
case 3: // 상
for (int j = 0; j < N; j++) {
int newi = N - 1;
for (int i = N - 1; i >= 0; i--) {
if (originMap[i][j] != 0)
moveMap[newi--][j] = originMap[i][j];
}
}
break;
}
return moveMap;
}
static int[][] mergeMap(int d, int[][] map) {
int ni = 0, nj = 0;
switch (d) {
case 0: // 우
for (int i = 0; i < N; i++) {
for (int j = 0; j < N - 1; j++) {
ni = i + dir[d][0];
nj = j + dir[d][1];
if (map[i][j] == map[ni][nj]) {
map[i][j] += map[ni][nj];
map[ni][nj] = 0;
}
}
}
break;
case 1: // 하
for (int j = 0; j < N; j++) {
for (int i = 0; i < N - 1; i++) {
ni = i + dir[d][0];
nj = j + dir[d][1];
if (map[i][j] == map[ni][nj]) {
map[i][j] += map[ni][nj];
map[ni][nj] = 0;
}
}
}
break;
case 2: // 좌
for (int i = 0; i < N; i++) {
for (int j = N - 1; j > 0; j--) {
ni = i + dir[d][0];
nj = j + dir[d][1];
if (map[i][j] == map[ni][nj]) {
map[i][j] += map[ni][nj];
map[ni][nj] = 0;
}
}
}
break;
case 3: // 상
for (int j = 0; j < N; j++) {
for (int i = N - 1; i > 0; i--) {
ni = i + dir[d][0];
nj = j + dir[d][1];
if (map[i][j] == map[ni][nj]) {
map[i][j] += map[ni][nj];
map[ni][nj] = 0;
}
}
}
break;
}
return map;
}
static void print(int[][] map) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
}
문제점 해결
1. 문제 이해도 부족
문제를 제대로 안읽는 안좋은 습관이 또 시간낭비라는 결과를 불러왔다 ㅠㅠ. 기존의 2048게임은 합쳐진 블록도 또 합쳐질 수 있는데 이 문제에선 한 번 합쳐진 블록은 다시 합쳐질 수 없음을 확인하지 않고 문제를 풀어서 몇시간을 날렸다.. 다시 한 번 느끼지만 문제를 꼼꼼하게 읽자!!!!
2. 재귀 호출 시 배열 복사
direction(0:우, 1:하, 2:좌, 3:상)을 우 우 우 우 우 에서 우 우 우 우 하 로 옮길 때 4번째 우 이동후의 배열이 아니라 5번째 우 이동 후의 배열이 저장되는 부분에서 문제가 있음을 발견했고 재귀호출시엔 배열을 복사해서 그 값을 retrun해줘야 함을 깨달았다. int[][] moveMap = moveMap(d, map); 이 부분에서 map을 그대로 갖다 쓰면 static선언처럼 map의 값이 바뀌었고 moveMap 함수에서 map을 복사하여 사용했더니 이 부분이 해결되었다.
3. 4% 지옥
뽑아낼 수 있는 경우의 수는 다 뽑아낸것같은데 왜 자꾸 틀리는지 이해를 못할때 쯤 여러 랜덤 반례들을 적용시키면서 하나하나 수정해갔다. 하지만 여전히 4%를 벗어나지 못했고 결국 코드를 갈아 엎는 선택을 했다.
3. 가끔은 코드를 분리하는것도 좋다
처음엔 합쳐진 후 0인 공간을 땡기는 작업을 같이했는데 (merge와 move를 함께 짬) 4%를 이기지 못한 난 코드를 분리하기로 결심했고 0인 공간을 땡기는 작업과 블록을 합치는 작업을 두개의 함수 moveMap과 mergeMap으로 나누어서 결국 성공했다 ㅠㅠ 정말 오랜 시간이 걸린 문제인만큼 다시 풀어봐야 함을 느꼈다.