leetcode 733(bfs), 695(bfs), 407 trapping rain water2(힙,구현,bfs), 945(구현)

733 https://leetcode.com/problems/flood-fill/

bfs문제이다.

from collections import deque

class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        original_color = image[sr][sc]
        q = deque([[sr, sc]])
        visited = set()
        while q:
            x,y = q.popleft()
            image[x][y] = newColor
            for _x, _y in [[-1, 0], [0, -1], [0, 1], [1, 0]]:
                next_x, next_y = x + _x, y + _y
                if (next_x, next_y) not in visited and 0 <= next_x < len(image) \
                    and 0 <= next_y < len(image[0]) and image[next_x][next_y] == original_color:
                    visited.add((next_x, next_y))
                    q.append([next_x, next_y])
        return image

695 https://leetcode.com/problems/max-area-of-island/

from collections import deque

class Solution(object):
    def maxAreaOfIsland(self, grid):
        island = [0]
        self.visited = set()
        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                if grid[i][j] == 1:
                    self.visited.add((i, j))
                    island.append(self.dfs(i, j, grid))
                    
        return max(island)
    
    def dfs(self, x, y, grid):
        queue = deque([[x, y]])
        island_count = 0
        while queue:
            island_count += 1
            x, y = queue.popleft()
            for _x, _y in [[-1, 0], [0, -1], [0, 1], [1, 0]]:
                next_x, next_y = x + _x, y + _y
                if (next_x, next_y) not in self.visited and 0 <= next_x < len(grid) \
                    and 0 <= next_y < len(grid[0]) and grid[next_x][next_y] == 1:
                    self.visited.add((next_x, next_y))
                    queue.append([next_x, next_y])
                    
        return island_count

407 https://leetcode.com/problems/trapping-rain-water-ii/

trapping rain water1번 문제를 기반으로 2차원으로 풀려고 했는데 안되었다. 못풀다가 discussion에 아주 좋은 유튜브 영상이 있어서 이걸 보고 풀었다. 영상

영상을 보고나서 아 이건 1번이랑 다른 문제구나.. 하는 생각과 생각한 사람은 진짜 개똑똑한것같다 ㅋㅋㅋ

푸는법은 가장 바깥쪽을 최소힙에 넣어놓고 가장 작은 값부터 빼낸다. 그리고 4방향 이웃을 방문하면서 푼다. 근데 가장 중요한 포인트는 현재 방문한 좌표에서 이웃이 max보다 적으면 그 차액만큼 물을 더해주는데, 이게 어떻게 그안에 물이 차있는걸 증명하지? 였는데 

최소 힙에 좌표를 넣어놓고 가장 낮은 높이부터 빼내서 연산하므로 이웃이 현재의 max보다 낮으면 그만큼 물이 찰수밖에 없다.(다시 강조하자면 낮은 높이부터 빼내어서 연산하므로) 코드는 간단하다...

from heapq import *

class Solution(object):
    def trapRainWater(self, heightMap):
        m, n = len(heightMap), len(heightMap[0])
        heap = []
        visited = set()

        for i in xrange(m):
            for j in xrange(n):
                if i == 0 or j == 0 or i == m-1 or j == n-1:
                    heappush(heap, (heightMap[i][j], (i, j)))
                    visited.add((i, j))
                    
        ret = 0
        _max = -1
        while heap:
            height, (x, y) = heappop(heap)
            _max = max(_max, height)
            
            for _x, _y in [[-1, 0], [0, 1], [0, -1], [1, 0]]:
                next_x, next_y = x + _x, y + _y
                if not 0 <= next_x < m or not 0 <= next_y < n or (next_x, next_y) in visited:
                    continue
                visited.add((next_x, next_y))
                if _max > heightMap[next_x][next_y]:
                    ret += _max - heightMap[next_x][next_y]
                heappush(heap, (heightMap[next_x][next_y], (next_x, next_y)))
        return ret

945 https://leetcode.com/problems/minimum-increment-to-make-array-unique/

생각하는 시간이 좀 걸렸다. 배열 A를 정렬한 다음에 예로 [3,2,1,2,1,7] 라고 하면

# 1,1,2,2,3,7  # 정렬한 후

         

# 0,1,1,2,2  # 우리가 원하는 배열 - 정렬한 후

        

# 1,2,3,4,5,6,7  # 우리가 원하는 배열

처럼 '우리가 원하는 배열' 안에 들어가도록 해야하는데 그냥 차만 계산하면 된다.

근데 정렬했을때의 숫자가 항상 1,2,3,4처럼 나올수는 없는 법이므로 v라는 변수를 둬서 다음 집어넣을 배열의 인덱스를 기억해놓는다. 

class Solution(object):
    def minIncrementForUnique(self, A):
        if not A:
            return 0
        A = sorted(A) 
        
        visited = set()
        ret = 0
        v = A[0]
        for a in A:
            if a not in visited:
                v = a + 1  # 한번도 방문 안한 경우 v를 그 다음 인덱스로 설정해줌.
                visited.add(a)
            else:
                ret += v - a  # 이미 방문했던 곳의 경우 v-a로 차이만큼 더해줌..
                visited.add(v)
                v += 1
        return ret

근데 다른 빠른 답을 보니 로직은 동일하게, in place로 배열을 변경하면서 풀면 visited라는 상태 체크 없이 풀수 있다.

from collections import defaultdict
class Solution(object):
    def minIncrementForUnique(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        A.sort()
        # prev = 0
        # cur = A[0]
        count = 0
        for i in range(1,len(A)):
            if A[i] <= A[i-1]:
                count += A[i-1]+1-A[i]
                A[i] = A[i-1]+1
        
        return count