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.
Constraints:
n == grid.lengthn == grid[i].length1 <= n <= 500grid[i][j] is either 0 or 1.배열, 깊이 우선 탐색, 너비 우선 탐색, Union-Find, 행렬
이 문제는 n x n 크기의 이진 행렬 grid가 주어질 때, 최대 한 개의 0을 1로 변경하여 만들 수 있는 가장 큰 섬의 크기를 반환하는 문제입니다. 섬은 4방향으로 연결된 1들의 그룹입니다.
n x n 크기의 이진 행렬 grid (원소는 0 또는 1).0을 1로 바꾼 후의 가장 큰 섬의 크기.n은 1부터 500까지.이 문제를 해결하기 위한 기본적인 접근 방식은 두 단계로 나눌 수 있습니다:
grid에 이미 존재하는 모든 섬을 식별하고, 각 섬의 고유 ID와 크기를 계산하여 저장합니다. 이는 나중에 0을 1로 바꿨을 때 주변 섬들을 쉽게 합칠 수 있도록 하기 위함입니다. BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)를 사용하여 연결된 1들을 탐색하고, 각 셀에 해당 섬의 ID와 크기 정보를 매핑하는 보조 board를 생성합니다.0 셀을 1로 바꿔보기: 모든 0 셀에 대해, 해당 0을 1로 바꿨을 때 형성될 수 있는 새로운 섬의 크기를 계산합니다. 이때, 0 주변의 인접한 섬들을 찾아 그 크기들을 합산합니다. 0 셀 자체도 1이 되므로 1을 더해줍니다. 인접한 섬들이 여러 개일 경우 중복 계산을 피하기 위해 set 자료구조를 사용하여 고유한 섬 ID만 추적합니다. 마지막으로 이 과정에서 얻은 모든 섬 크기 중 최댓값을 구합니다.이 접근 방식은 각 0을 1로 바꿀 때마다 처음부터 섬을 다시 계산하는 비효율적인 방법을 피하고, 미리 계산된 섬 정보를 활용하여 효율적으로 처리합니다.
주어진 코드는 위에서 설명한 두 가지 접근 방식을 순차적으로 구현합니다.
n = len(grid)로 그리드의 크기를 얻고, board와 visited 두 개의 n x n 행렬을 초기화합니다. board는 각 셀이 속한 섬의 (ID, 크기)를 저장하고, visited는 BFS 탐색 시 방문 여부를 기록합니다. num은 섬의 고유 ID를 부여하는 카운터입니다.grid의 모든 셀을 순회하면서 grid[i][j] == 1이고 아직 방문하지 않은(not visited[i][j]) 셀을 찾습니다.deque를 사용하여 BFS 큐를 관리하고, 현재 섬에 속하는 모든 셀의 좌표를 blocks 리스트에 저장합니다.blocks 리스트에 있는 셀들의 개수가 현재 섬의 크기(size)가 됩니다. 이 size는 현재까지 찾은 가장 큰 섬 answer와 비교하여 업데이트됩니다.blocks에 있는 모든 셀에 대해 board[x][y]에 현재 섬의 (num, size) 정보를 저장합니다. 그리고 다음 섬을 위해 num을 1 증가시킵니다.board에는 모든 기존 섬들의 ID와 크기 정보가 채워져 있습니다. 만약 grid가 모두 1로 이루어져 있다면, 이 단계에서 answer가 n*n이 되어 올바른 결과가 됩니다.0 셀을 1로 변경하여 최대 섬 크기 계산grid의 모든 셀을 다시 순회하며 grid[x][y] == 0인 셀(즉, 물 지역)을 찾습니다.0 셀에 대해, 해당 0을 1로 변경했을 때 형성될 수 있는 잠재적인 섬의 크기를 계산합니다.size = 1로 초기화하는데, 이는 변경된 0 셀 자체를 나타냅니다. seen = set()은 이 0 셀에 인접한 섬들의 고유 ID를 추적하여 중복 합산을 방지합니다.0 셀의 4방향 이웃(dx, dy로 정의된 방향)을 확인합니다.
0 <= nx < n and 0 <= ny < n), board[nx][ny]가 0이 아니라면, 이웃 셀은 기존 섬의 일부입니다.board[nx][ny]에서 해당 섬의 island ID와 cnt (크기) 정보를 가져옵니다.island ID가 seen(set)에 없다면, 아직 이 섬의 크기를 추가하지 않은 것이므로 seen에 추가하고 size에 cnt를 더해줍니다.size는 현재 0을 1로 변경했을 때 만들 수 있는 섬의 크기이므로, answer와 비교하여 최댓값을 업데이트합니다.0으로 이루어져 있다면, 이 단계에서 각 0을 1로 바꿀 때마다 size는 항상 1이 되며, answer는 최종적으로 1이 됩니다.시간 복잡도: O(N^2)
n x n 그리드의 모든 셀을 한 번씩 순회하며 BFS를 수행합니다. 각 셀은 BFS 큐에 한 번 추가되고 처리됩니다. 각 BFS 내에서 인접 셀을 확인하는 작업도 각 셀당 상수 번 수행됩니다. 따라서 이 단계의 시간 복잡도는 O(N^2)입니다.0 셀 변경 시뮬레이션): n x n 그리드의 모든 셀을 한 번씩 순회합니다. 각 0 셀에 대해 4방향 이웃을 확인하고 set에 추가하는 작업은 O(1)입니다. 따라서 이 단계의 시간 복잡도도 O(N^2)입니다.공간 복잡도: O(N^2)
board 행렬: n x n 크기로, 각 셀에 (ID, size) 튜플을 저장하므로 O(N^2) 공간이 필요합니다.visited 행렬: n x n 크기로, O(N^2) 공간이 필요합니다.q (BFS 큐): 최악의 경우(그리드 전체가 하나의 섬인 경우) n*n개의 셀을 저장할 수 있으므로 O(N^2) 공간이 필요합니다.blocks 리스트: 최악의 경우(하나의 섬이 n*n 셀을 차지) n*n개의 셀을 저장할 수 있으므로 O(N^2) 공간이 필요합니다.seen set: 최대 4개의 인접 섬 ID만 저장하므로 O(1) 공간이 필요합니다.0을 1로 바꾸는 모든 시나리오마다 섬의 크기를 처음부터 계산하는 대신, BFS를 사용하여 기존 섬들의 고유 ID와 크기를 미리 계산하고 board에 저장해둡니다. 이는 이후 계산을 위한 효율적인 룩업 테이블 역할을 합니다.board를 통한 섬 정보 매핑: board[r][c] = (island_id, size)와 같이 각 1 셀에 해당 섬의 ID와 크기를 직접 매핑함으로써, 어떤 0 셀이 1로 바뀌었을 때 인접한 섬들의 정보를 빠르게 가져올 수 있습니다.0 셀이 1로 바뀔 때, 동일한 섬에 여러 방향으로 인접할 수 있습니다 (예: 'L'자 형태의 섬). set 자료구조(seen)를 사용하여 이미 합산된 인접 섬의 ID를 기록하고, 중복으로 크기를 더하는 것을 방지합니다.from collections import deque
class Solution:
def largestIsland(self, grid: list[list[int]]) -> int:
n = len(grid)
board = [[0] * n for _ in range(n)]
visited = [[False] * n for _ in range(n)]
num = 1
answer = 0
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(n):
for j in range(n):
if grid[i][j] == 1 and not visited[i][j]:
q = deque([(i, j)])
visited[i][j] = True
blocks = [(i, j)]
while q:
x, y = q.popleft()
for dx, dy in dirs:
nx, ny = x + dx, y + dy
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))
blocks.append((nx, ny))
size = len(blocks)
answer = max(answer, size)
for x, y in blocks:
board[x][y] = (num, size)
num += 1
for x in range(n):
for y in range(n):
if grid[x][y] == 0:
seen = set()
size = 1
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n and board[nx][ny] != 0:
island, cnt = board[nx][ny]
if island not in seen:
seen.add(island)
size += cnt
answer = max(answer, size)
return answer