[python3] 1162. As Far from Land as Possible

풀이 일자: 23.02.10

난이도: [Medium]

분류: [DP, BFS]

문제 내용

0(물)과 1(땅)로 구성된 n*n 크기의 grid라는 배열을 줬을 때 땅과 가장 가까운 물타일들 중 땅과의 manhattan거리가 최대일때의 거리를 구하는 문제이다.

 

주의) 문제에 나와있긴 하지만 거리를 구할 때  manhattan거리를 사용하라고 했다.

Manhatten 거리 = |x0 - x1| + |y0 - y1|   

Euclidian 거리 =  ( (x0 - x1)²+(y0 - y1)²)^½

 

예를 들면 아래의 배열처럼 주어졌다고 가정해보자.

1	0	1
0	0	0
1	0	1

 

각 물타일과 해당 물타일과 가장 가까운 땅과의 거리를 적어보면 아래와 같이 될 것으로 최대일 때의 거리는 2이다.

1	0(1)	1
0(1)	0(2)	0(1)
1	0(1)	1

 

 

 

문제 해결 흐름

1. 어떻게 해야 땅으로부터 가장 먼 곳을 찾을 수 있을까?

→  현재 모든 땅부터 시작해서 땅과 가장 가까운 곳부터 물을 땅으로 바꿔나간다고 생각한다면 맨 마지막에 땅으로 채워지는 곳이 가까운 육지로부터 제일 먼 곳이겠다.

 

[과정]

1) 아래의 배열이 주어졌다고 생각해보자

1. 기존의 배열

2) 모든 땅에서 distance 1만큼 떨어진 물을 땅으로 채운다.

2. 모든 땅에서 distance 1만큼 물을 땅으로 채우기

3) 기존 땅에서는 distance 2, 직전에 넓힌 땅 기준 distance 1만큼 떨어진 물을 땅으로 채운다.

3. 넓혀진 땅에서 distance 1만큼 물을 땅으로 채우기

4) 기존땅에서는 distance3, 직전에 넓힌 땅 기준 distance 1만큼 떨어진 물을 땅으로 채운다.

4. 넓혀진 땅에서 distance 1만큼 물을 땅으로 채우기 끝!

5) 다 채워진 경우 해당 distance가 해당 물이 가장 가까운 땅과의 거리가 다른 물보다 가장 큰 거리가 된다.

 

2. 뭔가 처음에 땅이라는 기준점이 있고 그 땅을 기준으로 1씩 넓혀가는 느낌???

→  BFS가 적합할거고 시작점(땅)이 하나가 아니기 때문에 뭔가 Recursive한 방식으로는 처리가 안되겠다는 생각을 할 수 있다..  (DFS를 사용하면 한 시작점에서 다 칠해버리기 때문에 불가능하다)

→ 그럼 2번째 BFS 풀이 방식인 while문과 queue를 사용하여 시작점을 queue에 넣어놓고 넣어진 순서대로 꺼내고 넣고 하는 방식을 사용해야겠다. ( 기존의 땅을 꺼내서 칠하고 새로 칠해진 땅을 기준으로 또 칠해야하기 때문에 새로 칠해진 땅을 큐에 넣는 방식)

 

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid);
        lands = sum(map(sum, grid));                       # 땅의 갯수 세기 
        arr = [];                                          # queue 역할

        if lands == 0 or lands == n*n:                     #땅이 없거나 물이 없는 경우
            return -1;

        for i in range(n):                                 # 초기 땅의 위치를 조사
            for j in range(n):
                if grid[i][j] == 1:
                    arr.append([i,j,0]);                   # 맨 뒤는 depth를 의미
        
        def leftColor(x: int, y: int, depth: int):         #왼쪽이 칠해질 수 있는 경우
            if grid[x][y - 1] == 0:
                grid[x][y - 1] = depth + 1
                arr.append([x, y - 1, depth + 1]);		  # 칠해진 타일을 다시 queue에 넣음
        
        def rightColor(x: int, y: int, depth: int):       #오른쪽이 칠해질 수 있는 경우
            if grid[x][y + 1] == 0:
                grid[x][y + 1] = depth + 1
                arr.append([x, y + 1, depth + 1]);        # 칠해진 타일을 다시 queue에 넣음
        
        def leftrightColor(x: int, y: int, depth: int):
            if y == 0:
                rightColor(x, y, depth);
            elif 0 < y and y < n - 1:
                leftColor(x, y, depth);
                rightColor(x, y, depth);
            else:
                leftColor(x, y, depth);

        def upColor(x: int, y: int, depth: int):       #위쪽이 칠해질 수 있는 경우
            if grid[x - 1][y] == 0:
                grid[x - 1][y] = depth + 1
                arr.append([x - 1, y, depth + 1]);     # 칠해진 타일을 다시 queue에 넣음

        def downColor(x: int, y: int, depth: int):     #아랫쪽이 칠해질 수 있는 경우
            if grid[x + 1][y] == 0:
                grid[x + 1][y] = depth + 1
                arr.append([x + 1, y, depth + 1]);     # 칠해진 타일을 다시 queue에 넣음
            
        def updownColor(x: int, y: int, depth: int):
            if x == 0:
                downColor(x, y, depth);
            elif 0 < x and x < n - 1:
                upColor(x, y, depth);
                downColor(x, y, depth);
            else:
                upColor(x, y, depth);

        while(1):
            current = arr.pop(0);                    # queue역할을 하는 arr에서 pop
            x = current[0]; y = current[1]; depth = current[2];
            leftrightColor(x, y, depth);			  # 칠할 수 있는 구역을 다 칠하고
            updownColor(x, y, depth);
            if len(arr) == 0:						# queue가 비었다는 것은 다 칠해졌으니까
                return depth;                       # 해당 depth가 최대 길이를 의미

 

=> 보기 편하게 함수로 코드를 작성했지만 함수를 쓰지 않으면 570ms정도까지 줄여집니다. 

 

Time Complexity: O(N^2)

초기 땅의 위치를 조사하기 위해 2중 for문을 돌렸기 때문에 O(N^2)이다.

 

Space Complexity: O(N^2)

최악의 경우 주어진 배열에 1이 (n*n - 1)개까지 올 수 있으므로  queue의 역할을 하는  arr의 경우  O(N^2)의 공간복잡도를 가질 것이다.

 

 

 

다른 해결 방식

1. 이번에는 한번 Dynamic programming으로 풀어보자( Official Solution)

→ dist배열을 선언해서 최대거리로 채워놓고 dp방식으로 하나씩 최단 distance를 채워가는 방법

 

[과정]

1) 아래 grid가 주어졌고 dist는 distance의 최댓값(row + col)에  +1을 저장해둔 상태이다.

2) ((왼쪽과 위의 원소를 확인하면서 최소값)와 현재 위치의 최솟값)을 현재 위치에 넣는다.

step1. 오른쪽과 위쪽 원소중 작은 것을 선택하고 현재 위치의 원소와 또 비교해서 작은 것을 선택한다.

3. 이번에는 (2,2)지점부터 반대로 (오른쪽과 아래의 원소를 확인하면서 최소값)와 현재 위치와의 최솟값)을 넣는다.

4. 그중 나온 값중 최댓값이 ans일 것이다.

5. 만약 ans가 최댓값(row + col)+1이 나오거나 0인 경우  땅이나 물 둘 중 하나는 없는 경우이므로 -1을 리턴한다.

 

이를 코드로 옮겨본다면

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid);
        maxD = 2*n + 1;              # 가능한 최대 distance에 +1을 한다.

        dist = [[maxD for i in range(n)] for j in range(n)];

        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:  # grid가 1인 경우 원래 땅이니까 0으로 설정 
                    dist[i][j] = 0;
                else:			# 오른쪽과 위쪽을 확인해서 작은 것을 고르고 현재 위치와 또 비교해서 작은 것을 선택
                    dist[i][j] = min(dist[i][j], min(dist[i-1][j] + 1 if i > 0 else maxD, dist[i][j - 1] + 1 if j > 0 else maxD));
        
        ans = -1;
        for i in range(n)[::-1]:     #이번에는 반대로 채워나간다.
            for j in range(n)[::-1]:
                dist[i][j] = min(dist[i][j], min(dist[i + 1][j] + 1 if (i < (n-1)) else maxD, dist[i][j + 1] + 1 if (j < (n-1)) else maxD));
                ans = max(ans, dist[i][j]) #왼쪽과 아래쪽을 확인해서 작은 것을 고르고 현재 위치와 또 비교해서 작은 것을 선택

        ans = -1 if (ans in [0, maxD]) else ans;   # 만약 ans가 (최대 거리+1)이나 0인 경우 물이나 땅 둘 중 하나만 있는 경우
        return ans

 

=> BFS보다는 떠올리기는 어려운 방법으로 보인다. 하지만 충분히 가져갈만한 아이디어라고 생각한다.

 

Time Complexity: O(N^2)

dist 초기화 등으로 2중 for문을 돌렸기 때문에 O(N^2)이다.

 

Space Complexity: O(N^2)

거리를 저장하는 dist의 배열로 O(N^2)이다.

 

 

 

문제 링크

https://leetcode.com/problems/as-far-from-land-as-possible/description/

As Far from Land as Possible - LeetCode