백준 12100 2048

이번 문제를  풀면서 부족했던 점들을 먼저 나열하겠다.

 

첫 번째, 시간 복잡도를 제대로 계산하지 못했다. 왜냐하면 풀이에 확신이 없었기 때문이다. 주어진 조건 대로 블럭을 옮기면 풀릴 것 같았지만 dfs를 통해서 풀어야 했기 때문에 시간 초과에 대한 확신이 없었다. 그래서 해당 문제 풀이를 시작하기 까지 시간이 오래 걸렸다.

5번 이동이 가능하고 한 번 이동에 4방향이 가능 하므로 4^5가 우선적으로 걸린다고 생각했다. 그리고 20 x 20 배열이므로 400 * 4^5의 시간이 걸린다고 생각했다. 여기 까지는 충분하다고 생각했지만, 여기에 각 블럭을 이동하는 데 걸리는 시간이 곱해진다면 시간 초과가 나지 않을까 하는 생각이 들었고, 좀 더 쉽게 풀어 보려는 생각도 더해졌던 것 같다.

하지만 마땅한 방법이 생각나지 않았고 결국은 주어진 조건 그대로 시뮬레이션하는 코드를 짜기 시작했다.

결론적으로 좀 더 신중하게 시간 복잡도를 계산했다면 불필요하게 오래 생각하지 않고 코딩을 시작할 수 있었을 것이다.

 

두 번째, dfs에 대한 자만이 컸다. 평소에 bfs와 dfs에 대한 자신이 있었기 때문에 오답이 나왔을 때 dfs 구현에서 문제가 발생했을 것이라는 생각을 전혀하지 않았다.

하지만 dfs문 안에서 for문을 통해 다시 dfs를 재귀호출하는 경우에 여러 번 실수를 했던 경험이 있었다. 그럼에도 똑같은 실수를 반복했다. 자만하지 않고 풀어야 할 것 같다.

결국 dfs에서 에러가 발생한 것을 알지 못하고, 엉뚱하게 블럭을 옮기는 코드를 계속해서 수정하다보니 불필요한 시간이많이 소요되었다. 

 

세 번째, dfs시 디버깅에 대한 문제이다. 답이 맞지 않는 테스트 케이스를 돌려보았으나 어디서 답이 변경되는 것인지 찾는 과정이 너무 힘들었다. 배열을 다 출력해 보기도 하고, 직접 디버깅을 돌려보기도 했으나 너무 많은 출력과 코드로 인해서 찾다가 중간에 포기해버렸다.

다른 디버깅은 모르겠지만 dfs와 같은 재귀 호출에서의 디버깅에 아직 부족한 점이 많은 것 같다. 좀 더 공부해야 겠다.

============================================================================

다른 분들의 코드를 참조하면서 더 직관적이고 보기좋은 코드를 보았다.

if else 문들의 순서를 그다지 생각하지 않고 푸는 편이 었는데, 이번 문제에서는 if else 문을 통해 걸어주는 조건들의

순서를 잘 조절한다면 훨씬 코드가 간편했다. 

if else 문의 순서를 잘 고려해서 코드를 짜도록 해야겠다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int ans;
    static int n;
    static int[] dr = { -1, 0, 1, 0 };
    static int[] dc = { 0, 1, 0, -1 };
    static boolean flag;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        ans = 0;
        n = Integer.parseInt(st.nextToken());
        flag = true;
 
        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken().trim());
            }
        }
        solve(arr, 0);
 
//        멍청하게 dfs를 시작했다. dfs 문 안에 들어가서 for문을 통해서 시작해도 되는 거였는데
//        굳이 dir을 인자로 넣음으로써 멍청한 시작을 했다.
//        for(int i=0;i<4;i++) {
//            solve(arr, i, 0);
//        }
 
        System.out.println(ans);
    }
 
//    문제의 함수
//    solve(int[][]arr, int dir, int depth);
 
    private static void solve(int[][] arr, int depth) {
        if (depth == 5) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (ans < arr[i][j])
                        ans = arr[i][j];
                }
            }
            return;
        }
 
        int[][] cp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cp[i][j] = arr[i][j];
            }
        }
 
        for (int i = 0; i < 4; i++) {
            move(arr, i);
            solve(arr, depth + 1);
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    arr[j][k] = cp[j][k];
                }
            }
        }
    }
 
    private static void move(int[][] arr, int dir) {
        // 한 번 합쳐진 곳은 다시 합쳐지지 않도록 체크하는 배열
        boolean[] check = new boolean[n];
        // 방향 설정
        if (dir == 0) {// 위로
            for (int j = 0; j < n; j++) {// col
                check = new boolean[n];
                for (int i = 1; i < n; i++) {// row
                    if (arr[i][j] == 0)
                        continue;
                    int cur = i;
                    while (true) {//while문으로 블럭을 한 칸씩 이동시킨다.
                        if (cur == 0)//끝에 다다르면 종료
                            break;
                        //합쳐지지 않았고, 같은 숫자라면 더한다.
                        if ((!check[cur - 1] && !check[cur]) && arr[cur][j] == arr[cur - 1][j]) {
                            arr[cur - 1][j] *= 2;
                            arr[cur][j] = 0;
                            check[cur - 1] = true;
                        } else if (arr[cur - 1][j] == 0) {//0이라면 블럭을 이동시킨다.
                            arr[cur - 1][j] = arr[cur][j];
                            arr[cur][j] = 0;
                        } else//숫자가 있어서 막혔다면 밑에 있는 block을 이동하러 넘어간다.
                            break;
                        cur--;
                    }
 
                }
            }
        } else if (dir == 3) {// 왼쪽으로
            for (int i = 0; i < n; i++) {// row
                check = new boolean[n];
                for (int j = 1; j < n; j++) {// col
                    if (arr[i][j] == 0)
                        continue;
 
                    int cur = j;
                    while (true) {
                        if (cur == 0)
                            break;
                        if ((!check[cur - 1] && !check[cur]) && arr[i][cur - 1] == arr[i][cur]) {
                            arr[i][cur - 1] *= 2;
                            arr[i][cur] = 0;
                            check[cur - 1] = true;
                        } else if (arr[i][cur - 1] == 0) {
                            arr[i][cur - 1] = arr[i][cur];
                            arr[i][cur] = 0;
                        } else
                            break;
                        cur--;
                    }
 
                }
            }
        } else if (dir == 1) {// 오른쪽으로
            for (int i = 0; i < n; i++) {// row
                check = new boolean[n];
                for (int j = n - 2; j >= 0; j--) {// col
                    if (arr[i][j] == 0)
                        continue;
                    int cur = j;
                    while (true) {
                        if (cur == n - 1)
                            break;
                        if ((!check[cur + 1] && !check[cur]) && arr[i][cur + 1] == arr[i][cur]) {
                            arr[i][cur + 1] *= 2;
                            arr[i][cur] = 0;
                            check[cur + 1] = true;
                        } else if (arr[i][cur + 1] == 0) {
                            arr[i][cur + 1] = arr[i][cur];
                            arr[i][cur] = 0;
                        } else
                            break;
                        cur++;
                    }
 
                }
            }
        } else {// 밑으로
            for (int j = 0; j < n; j++) {// row
                check = new boolean[n];
                for (int i = n - 2; i >= 0; i--) {// col
                    if (arr[i][j] == 0)
                        continue;
                    int cur = i;
                    while (true) {
                        if (cur == n - 1)
                            break;
                        if ((!check[cur + 1] && !check[cur]) && arr[cur][j] == arr[cur + 1][j]) {
                            arr[cur + 1][j] *= 2;
                            arr[cur][j] = 0;
                            check[cur + 1] = true;
                        } else if (arr[cur + 1][j] == 0) {
                            arr[cur + 1][j] = arr[cur][j];
                            arr[cur][j] = 0;
                        } else
                            break;
                        cur++;
                    }
 
                }
            }
 
        }
 
    }
 
}