Leetcode Java 01 Matrix

문제

Link

코드

class Solution {

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

}

결과

Link

설명

1. mat 내 요소들 간 0과의 인접 거리를 구해서 값을 바꾸는 문제이다.

2. 문제 풀이에 필요한 변수를 정의한다.
   • row는 mat 행의 개수를 저장한 변수이다.
   • col은 mat 열의 개수를 저장한 변수이다.
   • distance는 첫 셀에서 끝 셀까지 최대 이동 거리가 될 수 있는 거리를 저장할 변수로, $row + col$로 정의한다.
3. 0부터 row 미만까지 i를 증가시키고, 0부터 col 미만까지 j를 증가시켜 좌측 위에서 우측 아래로 이동하며 아래를 수행한다.
   • mat[i][j]의 값이 0인 경우 자기 자신과 거리가 0이므로, 무시하고 넘어간다.
   • top과 left를 최대 이동 거리인 distance로 초기화 시킨다.
   • $i - 1$이 0 이상인 경우, top에 mat[$i - 1$][j]를 넣어준다.
   • $j - 1$이 0 이상인 경우, left에 mat[i][$j - 1$]를 넣어준다.
   • mat[i][j]에 top과 left중 작은 값인 가장 인접한 거리에 1을 더해서 넣어준다.
4. $row - 1$부터 0 이상까지 i를 감소시키고, $col - 1$부터 0 이상까지 j를 감소시켜 우측 아래에서 좌측 위로 이동하며 아래를 수행한다.
   • mat[i][j]의 값이 0인 경우 자기 자신과 거리가 0이므로, 무시하고 넘어간다.
   • bottom과 right를 최대 이동 거리인 distance로 초기화 시킨다.
   • $i + 1$이 0 이하인 경우, bottom에 mat[$i + 1$][j]를 넣어준다.
   • $j + 1$이 0 이하인 경우, right에 mat[i][$j + 1$]를 넣어준다.
   • mat[i][j]에 bottom, right중 작은 값인 가장 인접한 거리에 1을 더한 값과 mat[i][j]의 값 중 작은 값을 넣어준다.
5. 두 반복이 완료되면 완성된 mat를 주어진 문제의 결과로 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.