Java, LeetCode | 562. Longest Line of Consecutive One in Matrix

🚀 풀이 후기

상, 하, 좌, 우, 대각선으로 인접한 1의 개수 : DFS or BFS

오른쪽, 아래, 우하향 대각선으로만 나아가는 연속된 직선 1의 개수: 누적 DP

오른쪽, 아래, 우하향 대각선, 우상향 대각선 모두 검사해야 하는 연속된 직선 1의 개수: 독립된 DP

🌒 문제 설명

수평, 수직, 대각선 방향으로 검사했을 때 1로만 이루어진 가장 긴 연속된 cell 수를 반환하는 문제입니다. 

Given an m x n binary matrix mat, 
return the length of the longest line of consecutive one in the matrix.

The line could be horizontal, vertical, diagonal, or anti-diagonal.

Example 1

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

 

Example 2

Input: mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]
Output: 4

🌓 문제 풀이

class Node {
    int horizontal; // 수평
    int vertical; // 수직
    int diagonal; // 대각선 \
    int antiDiagonal; // 대각선 / 

    public Node() {
    }

    // @Override
    // public String toString() {
    // return String.format("[%d, %d, %d, %d]", horizontal, vertical, diagonal,
    // antiDiagonal);
    // }
}

class Solution {
    public Node[][] dp; // dp
    public int[][] map; // 입력값을 복사할 map
    public int answer; // 답
    public int[][] move = { // 이전 노드로 움직이는 좌표값
            { 0, -1 }, // 좌
            { -1, 0 }, // 상
            { -1, -1 }, // 좌, 상
            { -1, 1 } // 좌, 하
    };

    public int longestLine(int[][] mat) {
        dp = new Node[mat.length][mat[0].length];
        map = new int[mat.length][mat[0].length];
        answer = 0;
        
        // map에 mat의 내용들을 복사합니다.
        // 깊은 복사가 아닌, mat의 주소값을 사용해도 괜찮습니다.
        for (int y = 0; y < mat.length; y++) {
            map[y] = Arrays.copyOf(mat[y], mat[0].length);
        }

        for (int y = 0; y < mat.length; y++) {
            for (int x = 0; x < mat[0].length; x++) {
                dp[y][x] = new Node();
                int value = map[y][x];
                if (value == 0) // 현재 좌표에 들어있는 값이 0이면 dp에 [0,0,0,0]이 들어있으면 됩니다.
                    continue;
                    
                // 좌표값이 1이면, 이전 좌표값을 바탕으로 현재 좌표값 dp 에 새로운 값을 저장합니다.
                dp[y][x].horizontal = getValue(y, x, 0, value);
                dp[y][x].vertical = getValue(y, x, 1, value);
                dp[y][x].diagonal = getValue(y, x, 2, value);
                dp[y][x].antiDiagonal = getValue(y, x, 3, value);

                // System.out.print(dp[y][x]);
            }
            // System.out.println();
        }

        return answer;
    }

    public int getValue(int y, int x, int i, int plus) {
        int max = plus;
        
        // 직선을 그었을 때 이전 좌표값인 py, px를 설정합니다.
        int py = y + move[i][0];
        int px = x + move[i][1];
        
        // 이전 좌표가 map 내부 좌표고, 이전 좌표값이 1이면 이전 좌표값+plus한 값을 max에 저장합니다.
        if (isInMap(py, px) && map[py][px] == 1) {
            if (i == 0) {
                max = dp[py][px].horizontal + plus;
            } else if (i == 1) {
                max = dp[py][px].vertical + plus;
            } else if (i == 2) {
                max = dp[py][px].diagonal + plus;
            } else {
                max = dp[py][px].antiDiagonal + plus;
            }
        }
        
        // 현재 답과, max중 더 큰 값으로 답을 갱신합니다.
        answer = Math.max(answer, max);

        return max;
    }

    public boolean isInMap(int y, int x) {
        if (y < 0 || x < 0 || y >= dp.length || x >= dp[0].length) {
            return false;
        }
        return true;
    }
}

- 시간복잡도: O(M*N)

- 공간복잡도: O(M*N*4)

 

---

리트코드 문제

깃허브 코드