Leetcode 1162) As Far from Land as Possible

06 Aug 2021 in Algorithms

내 답안

class Solution {
    public int maxDistance(int[][] grid) {
        int[][] dist = new int[grid.length][grid[0].length];
        int[][] pos = {{1,0},{-1,0},{0,1},{0,-1}};
        Queue<int[]> q = new LinkedList<>();
        boolean visited[][]=new boolean[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==1){
                    q.add(new int[]{i,j});
                    visited[i][j]=true;
                }                
            }
        }
        int cnt=0;
        while(!q.isEmpty()){
            int size= q.size();
            for(int _i =0;_i<size;_i++){
                int[] ind = q.poll();
                visited[ind[0]][ind[1]]=true;
                dist[ind[0]][ind[1]]+=cnt;
                for(int[] near : pos){
                    int a= ind[0]+near[0];
                    int b= ind[1]+near[1];
                    if(!(a<0 || a>=grid.length || b<0 || b>= grid[0].length)){
                        if(!visited[a][b]){
                            visited[a][b]=true;
                            q.add(new int[]{a,b});
                        }
                    }
                }
            }
            cnt++;
        }
        int max=-1;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(dist[i][j]>max){
                    max=dist[i][j];
                }            
            }
        }
        max= max==0?-1:max;
        return max;

    }
}

다른 답안

class Solution {
    public int maxDistance(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dist = new int[m][n];

        for (int i = 0; i < m; i++) {
            Arrays.fill(dist[i], m * n);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                } else {
                    if (i > 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i-1][j] + 1);
                    } 
                    if (j > 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
                    }
                }
            }
        }

        int currMax = -1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] != 1) {
                    if (i < n - 1) {
                        dist[i][j] = Math.min(dist[i][j], dist[i+1][j] + 1);
                    } 
                    if (j < m - 1) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j+1] + 1);
                    }
                    currMax = dist[i][j] != m * n ? 
                        Math.max(currMax, dist[i][j]): currMax;
                }
            }
        }
        return currMax;
    }
}