[Java] LeetCode 1162. As Far from Land as Possible

[Java] LeetCode 1162. As Far from Land as Possible

 

문   제 : 

이차원 정수 배열 grid[n][n]가 주어진다.

grid[n][n]의 값은 0 or 1로 이루어져 있는데, 0은 물, 1은 땅을 뜻한다.

모든 땅과 가장 멀리 있는 물을 w라고 한다면

w와 땅의 가장 가까운 거리를 구해라.

 

Constraint

{ n == grid.length }

{ n == grid[i].length }

{ 1 <= n <= 100 }

{ grid[i][j] is 0 or 1 }

 

 

Example )

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

//////////////////////////////////////////////////////////

Input: grid = [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.

 

---

접   근 : 

물의 좌표를 찾아서, 땅과의 거리를 구한다음, 그 거리가 최대가 되도록 업데이트 시켜준다.

---

해   결 : 

땅들을 모두 비교해야 하기 때문에 땅을 관리할 수 있는 land Class 를 생성

land Class는 땅의 좌표를 가지고 있다.

 

land를 ArrayList에 넣고 정렬한다. -> 좌표순서대로

 

grid를 돌면서 값이 0이라면, 즉 물 이라면,

가장 가까운 땅과의 거리를 구하는 함수를 실행한다.

 

가장 가까운 땅과의 거리를 구하는 함수 : 

땅 List에 있는 땅 하나하나와 자신의 좌표를 비교해 가장 최소가 되는 거리를 구한다.

여기서 만약  이미 땅과 더 가까운 물이면 (distance 보다 작음) 어차피 남은 땅들과 비교해도 distance는 업데이트 되지 않는다. 그러므로 return 해준다.

 

이렇게 모든 물의 좌표를 모든 땅의 좌표와 비교해 거리를 구하는 브루트포스 방식으로 해결.

 

 

---

lands List 생성 및 추가

 

for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        if(grid[i][j] == 1) lands.add(new land(i, j));
    }
}

 

---

 

예외처리 - 만약 모든 칸이 물이거나 땅이라면 

 

if(lands.size() == 0 || lands.size() == n*n) return -1;

 

 

---

함수 작성

 

public int nearestLandDis(int x, int y, List<land> lands, int distance){ // 물 좌표
    int dis;
    int res = Integer.MAX_VALUE;
    for(int i=lands.size()-1; i>=0; i--){
        // 물과 땅 사이의 거리
        dis = Math.abs(lands.get(i).x - x) + Math.abs(lands.get(i).y - y);
        res = Math.min(dis, res); // 가장 가까운 땅과의 거리를 구함
        if(res < distance) return -1; // 이미 존내 가까운 물이면 distance를 업데이트 시킬 수 없음
    }
    return res;
}

---

결   과  :

class Solution {
    public int maxDistance(int[][] grid) {
        int distance = -1;
        int n = grid.length;
        List<land> lands = new ArrayList<>();
        

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == 1) lands.add(new land(i, j));
            }
        }
        if(lands.size() == 0 || lands.size() == n*n) return -1;
        Collections.sort(lands);

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == 0) { // 물이면
                    distance = Math.max(distance, nearestLandDis(i, j, lands, distance));
                }
            }
        }

        return distance;

    }
    public int nearestLandDis(int x, int y, List<land> lands, int distance){ // 물 좌표
        int dis;
        int res = Integer.MAX_VALUE;
        for(int i=lands.size()-1; i>=0; i--){
            // 물과 땅 사이의 거리
            dis = Math.abs(lands.get(i).x - x) + Math.abs(lands.get(i).y - y);
            res = Math.min(dis, res); // 가장 가까운 땅과의 거리를 구함
            if(res < distance) return -1; // 땅과의 거리가 distance보다 가까운 물이면 distance를 업데이트 시킬 수 없음
        }
        return res;
    }

    class land implements Comparable<land>{
        public int x;
        public int y;

        public land(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int compareTo(land l){
            if(this.x > l.x) return 1;
            else {
                return -1;
            }
        }
    }
}