Making A Large Island - python solution

문제 링크 : https://leetcode.com/problems/making-a-large-island/

Making A Large Island - LeetCode

문제 해설

n x n 크기의 행렬이 주어집니다. 단 한 번 행렬의 요소 0을 1로 바꿀 수 있습니다.

이 과정을 적용해서 얻을 수 있는 가장 큰 섬(island)의 크기를 반환하세요.

섬은 4방향으로 이어진 1로 이루어진 집합입니다.

 

제한 사항

n == grid.length

n == grid[i].length

1 <= n <= 500

grid[i][j] is either 0 or 1

 

난이도 Hard

 

 

 

 

접근 방법

처음 떠올린 방법은 bfs로 섬의 크기를 구하는 함수를 작성하고

행렬 속 모든 0에 대해서 1로 바꾸었을 때 섬의 크기를 각각 구한 뒤 비교하여 최댓값을 얻는 방법을 떠올렸습니다.

 

1) 그런데 최초로 섬의 크기를 구할 경우 O(N^2)만큼 시간이 소요되고

2) 다시 행렬을 재탐색하며 모든 0에 대해서 1로 치환했을 때마다 섬의 크기를 다시 계산하므로

최악의 경우 O(N^4) 만큼 시간이 소요됩니다.

이 경우 시간 초과 판정을 받을 수 있기 때문에 다른 방법을 모색해야 했습니다.

 

최초의 상황에서 섬의 크기를 구하고 0을 1로 바꿨을 때 합쳐지는 섬을 따로 구분할 수 있다면

2)의 과정에서 소요되는 시간을 크게 줄일 수 있다는 아이디어가 떠올랐습니다.

 

def search_island(self, grid: List[List[int]], r: int, c: int, num: int) -> int:
    dRow = [0, 0, 1, -1]
    dCol = [1, -1, 0, 0]
    n = len(grid)
    
    queue = deque()
    queue.append((r, c))
    grid[r][c] = num
    SIZE = 1
    
    while queue:
        row, col = queue.popleft()
        for d in range(4):
            newR = row + dRow[d]
            newC = col + dCol[d]
            if newR < 0 or newC < 0 or newR >= n or newC >= n:
                continue
            elif grid[newR][newC] != 1:
                continue
            grid[newR][newC] = num
            queue.append((newR, newC))
            SIZE += 1

    return SIZE

search_island 함수는 r행 c열부터 시작해서 섬을 탐색하고 그 크기를 반환하는 함수입니다.

행렬 정보를 담은 grid와 위치 정보를 담은 r,c 그리고 섬 번호를 담은 num을 매개변수로 받습니다.

 

bfs를 이용해서 4방향 탐색을 실행합니다.

이 때, 방문처리를 위한 visited 리스트를 사용하지 않고 주어진 grid를 수정해서 방문 처리를 실시합니다.

(섬 정보를 저장하기 위한 새 리스트를 생성하지 않으므로 메모리를 절약할 수 있습니다.)

grid의 값이 0이면 빈 곳, 1이면 아직 탐색하지 않은 땅을 의미하고

grid의 값 n이 2 이상이면 탐색한 땅이며 섬 번호 n에 속함을 의미합니다.

 

def largestIsland(self, grid: List[List[int]]) -> int:
    n = len(grid)
    sizes = [0, 0]
    
    num = 2
    for r in range(n):
        for c in range(n):
            if grid[r][c] != 1:
                continue
            size = self.search_island(grid, r, c, num)
            sizes.append(size)
            num += 1

    max_size = max(sizes)

    dRow = [0, 0, 1, -1]
    dCol = [1, -1, 0, 0]
    for r in range(n):
        for c in range(n):
            islands_to_merge = set()
            if grid[r][c] != 0:
                continue
            for d in range(4):
                newR = r + dRow[d]
                newC = c + dCol[d]
                if newR < 0 or newC < 0 or newR >= n or newC >= n:
                    continue
                elif grid[newR][newC] == 0:
                    continue
                islands_to_merge.add(grid[newR][newC])

            size = 1
            for island in islands_to_merge:
                size += sizes[island]
            max_size = max(max_size, size)
    
    return max_size

sizes 리스트는 각 섬의 크기 정보를 저장하기 위한 리스트입니다.

이 때 섬 정보 조회를 용이하게 하기 위해 사용될 일 없는 0번 인덱스와 1번 인덱스는 임의로 0으로 채워넣었습니다.

(grid에서 0은 빈 땅, 1은 탐색하지 않은 땅을 의미하므로 크기를 조회할 일이 없습니다.)

 

섬 번호를 의미하는 num은 2부터 시작하도록 했습니다.

grid를 탐색하며 1을 만나면 search_island 함수를 통해 섬을 방문처리하고 크기를 계산하여 sizes에 추가하도록 했습니다.

 

max_size는 최초 상황에서 가장 큰 섬의 크기를 저장합니다.

 

다시 grid를 탐색하며 0을 1로 바꿨을 때 합쳐지는 섬의 크기를 구했습니다.

(이전 과정을 통해 grid에 요소 1은 남아있지 않습니다.)

탐색 중에 0을 만나면 4방향으로 탐색하여 서로 다른 섬이 있는지 확인하고 size에 그 크기를 더하고

합쳐진 섬의 크기를 max_size와 비교하여 최댓값으로 갱신했습니다.

 

 

 

결과

 

from typing import List
from collections import deque

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        sizes = [0, 0]
        
        num = 2
        for r in range(n):
            for c in range(n):
                if grid[r][c] != 1:
                    continue
                size = self.search_island(grid, r, c, num)
                sizes.append(size)
                num += 1

        max_size = max(sizes)

        dRow = [0, 0, 1, -1]
        dCol = [1, -1, 0, 0]
        for r in range(n):
            for c in range(n):
                islands_to_merge = set()
                if grid[r][c] != 0:
                    continue
                for d in range(4):
                    newR = r + dRow[d]
                    newC = c + dCol[d]
                    if newR < 0 or newC < 0 or newR >= n or newC >= n:
                        continue
                    elif grid[newR][newC] == 0:
                        continue
                    islands_to_merge.add(grid[newR][newC])

                size = 1
                for island in islands_to_merge:
                    size += sizes[island]
                max_size = max(max_size, size)
        
        return max_size

    def search_island(self, grid: List[List[int]], r: int, c: int, num: int) -> int:
        dRow = [0, 0, 1, -1]
        dCol = [1, -1, 0, 0]
        n = len(grid)
        
        queue = deque()
        queue.append((r, c))
        grid[r][c] = num
        SIZE = 1
        
        while queue:
            row, col = queue.popleft()
            for d in range(4):
                newR = row + dRow[d]
                newC = col + dCol[d]
                if newR < 0 or newC < 0 or newR >= n or newC >= n:
                    continue
                elif grid[newR][newC] != 1:
                    continue
                grid[newR][newC] = num
                queue.append((newR, newC))
                SIZE += 1

        return SIZE

 

평가

runtime과 memory 사용량에서 매우 효율적인 코드임이 확인되었습니다.

Hard 난이도였는데 깔끔하고 좋은 코드로 빠르게 통과해서 정말 기분이 좋았습니다 !