[LeetCode] 827. Making A Large Island (Python)

 

난이도: Hard

문제 설명

---

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

 

Return the size of the largest island in grid after applying this operation.

 

An island is a 4-directionally connected group of 1s.

 

문제 예제

---

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.

 

제한 사항

---

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] is either 0 or 1.

 

Solution(솔루션)

---

def check_only_one_num(n, grid):
    only_one, only_zero = False, False

    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                only_zero = True
            else:
                only_one = True
        
    if only_zero and not only_one:
        return 1
    elif not only_zero and only_one:
        return n*n
    else:
        return False

def bfs(grid, n, i, j, visited, moves, root):
    visited[i][j] = True
    q = deque([(i,j)])
    area = 0
    path = []

    while q:
        x, y = q.popleft()
        area+=1
        path.append((x, y))

        for move in moves:
            nx = x + move[0]
            ny = y + move[1]

            if 0<=nx<n and 0<=ny<n and not visited[nx][ny] and grid[nx][ny] == 1:
                visited[nx][ny] = True
                q.append((nx, ny))

    for x, y in path:
        grid[x][y] = area
        root[x][y] = (n*i + j)

def get_area(grid, n, i, j, root, moves):
    check_root = set()
    area = 1

    for move in moves:
        nx = i + move[0]
        ny = j + move[1]

        if 0<=nx<n and 0<=ny<n and grid[nx][ny] != 0:
            r = root[nx][ny]
            if r not in check_root:
                check_root.add(r)
                area += grid[nx][ny]
    
    return area

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)

        check = check_only_one_num(n, grid)
        if check != False:
            return check

        moves = [[0,1], [0,-1], [1,0], [-1,0]]
        visited = [[False]*n for _ in range(n)]
        root = [[0]*n for _ in range(n)]

        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1 and not visited[i][j]:
                    bfs(grid, n, i, j, visited, moves, root)
        
        answer = 0
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 0:
                    area = get_area(grid, n, i, j, root, moves)
                    answer = max(answer, area)

        return answer

 

재미있는 문제였던 것 같다.

 

먼저 grid가 모두 0으로 되어있다면 1을 return하게 하고, 모두 1로 되어있다면 n*n을 return하도록 했다.

 

처음에는 다음과 같이 모든 0에 대해 이 0을 1로 바꾼다고 했을 때를 가정하고 bfs를 돌려 제일 큰 영역을 찾았다.

 

하지만, 이 방법은 TLE가 발생했다. 확실히 0이 많다고하면 오래 걸릴 것 같긴 했다.

 

그래서 다른 방법을 생각하다가 아래 그림과 같이 먼저 1로 이루어진 영역을 찾아 그 영역의 크기를 저장해놓고, 모든 0에 대해서 (1 + 상하좌우의 영역)의 크기하면 되지 않을까 였다.

 

 

하지만 이 역시 문제가 있었다. 모든 0에 대해서 (1+상하좌우 영역의 크기)를 진행하는데 만약 상하좌우의 영역들이 이미 연결되있는 영역이면 이를 다 더할 필요가 없다는 것이다.

 

따라서, 각 영역에 대해 root를 만들었다. 만약 (0, 0)에서 부터 시작해 영역이 만들어 졌다면 그 영역의 인덱스들은 같은 root로 치는 것이다.

 

이제 다시 모든 0에서 부터 상하좌우의 값을 더해주는데, check_root를 만들어 check_root에 없는 root를 가진 영역이면 더해주고 check_root에 이를 넣어주었다. 만약 check_root에 있는 root를 가진 영역이면 더해주지않고 넘어갔다.

 

이런식으로 모든 0에서 진행했고 제일 큰 area 값을 answer로 return하여 정답을 맞출 수 있었다.

---

문제: 827. Making A Large Island

 

깃허브: github

algorithmPractice/LeetCode/854-making-a-large-island at main · laewonJeong/algorithmPractice