Diagonal Traverse

4개의 edge에서 어떻게 대처할 것인가

1. On top bolder in up trend: go right
2. On right bolder in up trend: go down
3. On left bolder in down trend: go down
4. On bottom bolder in down trend: go right

***

1번과 2번이 동시에 발생하면 2번을 따르고

3번과 4번이 동시에 발생하면 4번을 따라야 한다.

 

1. DFS 방법으로 하려고 했음

-> 왜인지 모르겠으나 아래와 같은 오류 발생   => FAILED

WARNING: A command line option has enabled the Security Manager
WARNING: The Security Manager is deprecated and will be removed in a future release
java.lang.StackOverflowError

class Solution {
    int [] result;
    int m;
    int n;
    public int[] findDiagonalOrder(int[][] mat) {
        if (mat.length==0||mat[0].length==0)return new int[0];
        m = mat.length; //층
        n = mat[0].length; //호
        result = new int[m*n];
        boolean upward = true;
        dfs(0,0,0,upward, mat);
      
       return result;

    }
    
    private void dfs(int x, int y, int index,boolean upward,  int[][]mat) {
        
        result[index]=mat[x][y];
        
        if(x==m-1 && y==n-1) {
            return;
        }
        //4가지 경우가 있음
        //위로 올라가면서, top에 닿으면 오른쪽으로
        //위로 올라가면서, 오른쪽에 닿으면 아래로
        //아래로 내려가면서, 왼쪽에 닿으면 아래로
        //아래로 내려가면, 바닥에 닿으면 오른쪽으로
        //1,2 동시면 2번 따라
        //3,4, 동시면 4번 따라
        if(upward==true){
            if(y==n-1) {  
                dfs(x++,y,index++,false, mat);
            }else if(x==0) {
                dfs(x, y++, index++, false,mat);
            }else{
                dfs(x--, y++, index++, true,mat);
            }   
            
        }else {
            if(x==m-1) {
                dfs(x,y++, index++, true,mat);
            }else if(y==0) {
                dfs(x++,y,index++, true, mat);
            }else{
                dfs(x++,y--,index++, false, mat);
            } 
        }
    }
}

 

 

2. 일반적인 방법 (2ms, 96.05%)

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix.length==0||matrix[0].length==0)return new int[0];
        int col=matrix.length,row=matrix[0].length;
        int nums=col*row,m=0,n=0;
        int res[]=new int[nums];
        boolean flag=true;

        for(int i=0;i<nums;i++){
            res[i]=matrix[m][n];
            //올라가고 내려가는 거에 따라 대각선으로 이동
            if(flag){
                n+=1; m-=1; 
            }else{
                n-=1; m+=1;
            }
            //대각선으로 이동한 값이 사각형 범위를 벗어나면 원래 자리로 돌아간 다음,
            //바닥면에 닿으면 오른쪽으로 한 칸 이동
            // 오른쪽 면에 닿으면 아래로 한 칸 이동
            if(m>=col){
                m-=1; n+=2; flag=true;
            }else if(n>=row){
                n-=1; m+=2; flag=false;
            }
            //그러고 나서도, 각 각 0보다 작으면 0값으로 변경
            if(m<0){
                m=0; flag=false;
            }else if(n<0){
                n=0; flag=true;
            }
        }
        return res;
    }
}

3. solution에 나온 방법

굉장히 생각해 볼 법한 방법이다.

위로 갔다가 아래로 갔다가 출력하는 거지만,

그냥 모든 요소가 위에서 아래로 내려가는 대각선으로 출력된다고 가정한다.

대각선마다 배열을 만들어 놓고,

그 대각선의 순서가 짝수이면, 그 배열을 reverse 한 값을 넣어주면 된다!!!

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        
        // Check for empty matrices
        if (matrix == null || matrix.length == 0) {
            return new int[0];
        }
        
        // Variables to track the size of the matrix
        int N = matrix.length;
        int M = matrix[0].length;
        
        // The two arrays as explained in the algorithm
        int[] result = new int[N*M];
        int k = 0;
        ArrayList<Integer> intermediate = new ArrayList<Integer>();
        
        // We have to go over all the elements in the first
        // row and the last column to cover all possible diagonals
        for (int d = 0; d < N + M - 1; d++) {
            
            // Clear the intermediate array every time we start
            // to process another diagonal
            intermediate.clear();
            
            // We need to figure out the "head" of this diagonal
            // The elements in the first row and the last column
            // are the respective heads.
            int r = d < M ? 0 : d - M + 1;
            int c = d < M ? d : M - 1;
            
            // Iterate until one of the indices goes out of scope
            // Take note of the index math to go down the diagonal
            while (r < N && c > -1) {
                
                intermediate.add(matrix[r][c]);
                ++r;
                --c;
            }
                
            // Reverse even numbered diagonals. The
            // article says we have to reverse odd 
            // numbered articles but here, the numbering
            // is starting from 0 :P
            if (d % 2 == 0) {
                Collections.reverse(intermediate);
            }
            
            for (int i = 0; i < intermediate.size(); i++) {
                result[k++] = intermediate.get(i);
            }
        }
        return result;
    }
}