[Algorithm][Graph][Java] 문제 풀이 #29 - 542. 01 Matrix

문제 링크

https://leetcode.com/problems/01-matrix/

 

문제 풀이

public int[][] updateMatrix(int[][] mat) {
    int row = mat.length;
    int col = mat[0].length;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (mat[i][j] == 0) continue;
            mat[i][j] = row + col;
            if (i > 0) mat[i][j] = Math.min(mat[i][j], mat[i - 1][j] + 1);
            if (j > 0) mat[i][j] = Math.min(mat[i][j], mat[i][j - 1] + 1);
        }
    }
    for (int i = row - 1; i >= 0; i--) {
        for (int j = col - 1; j >= 0; j--) {
            if (mat[i][j] == 0) continue;
            if (i < row - 1) mat[i][j] = Math.min(mat[i][j], mat[i + 1][j] + 1);
            if (j < col - 1) mat[i][j] = Math.min(mat[i][j], mat[i][j + 1] + 1);
        }
    }
    return mat;   
}

결과

그래프형 문제이다 보니 4방향만 잘 맞으면 풀이가 깔끔할 것이라고 생각하고 풀는 도중에 점점 더 지저분해 지고 테스트 케이스의 절반 정도 밖에 맞추지 못해 정답 풀이를 확인하고 Dynamic Programming 알고리즘을 더 파야 이런 유형의 문제를 쉽게 풀 수 있을것 같습니다.