[LeetCode] 542. 01 Matrix - 문제풀이

Description

0부터의 거리를 나타내도록 행렬표를 업데이트 하는 문제입니다.

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

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

Example 2:

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

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

Solution 1. BFS(Breadth-First Search) - 0부터 접근

private final int[][] DIRECTIONS = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};

public int[][] updateMatrix(int[][] mat) {

    int m = mat.length;
    int n = mat[0].length;

    Queue<int[]> q = new LinkedList<>();

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if(mat[i][j]==0){  // 0부터의 거리므로 시작점 0을 큐에 넣어줌
                q.offer(new int[]{i,j});
            }else{ // marking 아직 거리가 표기되지 않은 것을 대상으로 큐 확장을 위함
                mat[i][j] = -1;
            }
        }
    }

    while(!q.isEmpty()){ // 0부터 꺼내가며 BFS로 확장해 나감

        int[] curr = q.poll();

        for(int[] d:DIRECTIONS){
            int nr = curr[0]+d[0];
            int nc = curr[1]+d[1];
            if( nr < 0 || nc < 0 || nr >= mat.length || nc >= mat[0].length || mat[nr][nc] != -1) continue; // -1로 표기된것만 대상
            mat[nr][nc] = mat[curr[0]][curr[1]]+1; // 이전거리를 다음큐에 가져올수가 없으니 먼저 데이터를 넣어줌!
            q.offer(new int[]{nr,nc});
        }
    }
    
    return mat;
}

접근 아이디어 포인트는 0부터의 거리를 표기하는 것이기때문에 주어진 매트릭스에서 0의 위치를 모두 큐에 넣고 해당 위치부터 너비우선 탐색(BFS)을 통해 거리를 확장해 나가는 것 입니다.

0을 전부 큐에 넣어 위치를 기억하고 나머지 노드들은 -1로 표기하고 0부터 시작하여 거리를 표기해 나갑니다. 이미 표기된 부분이 있다면 스킵하고 아니면 이전 거리에서 +1하면서 끝까지 넓혀 나가면 됩니다.

Solution 2. BFS(Breadth-First Search) - 순차적접근

public int[][] updateMatrix2(int[][] mat) {

  int m = mat.length;
  int n = mat[0].length;

  for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
          if(mat[i][j]!=0){
              mat[i][j] = bfs(mat,i,j);
          }
      }
  }
  return mat;
}

private int bfs(int[][] mat,int r, int c){

  Queue<int[]> q = new LinkedList<>(); //좌표
  q.offer(new int[]{r,c}); //현재 시작점
  int[] curr = new int[]{r,c};
  while(!q.isEmpty()){
      curr = q.poll();
      if(mat[curr[0]][curr[1]] == 0){
          break;
      }
      for(int[] d:DIRECTIONS){  //시계방향으로 큐에 넣으면서 순회
          int x = curr[0]+d[0];
          int y = curr[1]+d[1];
          if( x < 0 || y < 0 || x >= mat.length || y >= mat[0].length) continue;
          q.offer(new int[]{x,y});
      }
  }
  return Math.abs(r-curr[0])+Math.abs(c-curr[1]);
}

행렬의 반전 없이 1일 경우 가장 가까운 0을 찾아나가는 방법입니다. 50개중 마지막 테스트케이스에서 Time Limit Exceeded 발생하긴 하는데 이런식으로 접근도 가능하다고 참고만 해주세요.

Reference

01 Matrix - LeetCode