Number of Islands
길이가 같은 문자열의 목록으로 지도를 받습니다. 여기서 '1'은 땅의 칸이고 '0'은 물의 칸입니다. 두 땅의 칸이 위, 아래, 왼쪽 또는 오른쪽으로 변을 공유하면 같은 섬에 속합니다. 모서리에서만 만나는 칸은 연결된 것으로 보지 않습니다. 섬의 개수를 반환하세요.
함수
- gridstring-array
- 맵, 행마다 문자열 하나씩
- 반환값integer
- 섬의 개수
제약 조건
1 ≤ grid.length ≤ 1501 ≤ grid[i].length ≤ 150- 모든 행의 길이는 같습니다.
- 모든 문자는
'0'또는'1'입니다.
예제
- 입력
- grid = ["11000", "11000", "00100", "00011"]
- 출력
- 3
- 설명
- 왼쪽 위의 네 개의 정사각형은 하나의 섬을 이룹니다. 세 번째 행의 가운데 정사각형은 모서리에서만 이들과 맞닿아 있으므로 두 번째 섬입니다. 오른쪽 아래의 한 쌍은 세 번째 섬입니다.
- 입력
- grid = ["01110", "01000", "00011", "11001"]
- 출력
- 3
- 설명
- 맨 위 행의 세 칸과 그 왼쪽 끝 아래에 있는 한 칸이 하나의 섬을 이룹니다. 세 번째 행의 오른쪽 두 칸은 아래쪽 오른쪽 칸과 연결되어 두 번째 섬을 이룹니다. 아래쪽 왼쪽 두 칸이 세 번째 섬입니다.
후속 질문
이제 물 지도에 육지가 한 칸씩 나타납니다. 지도를 처음부터 다시 훑지 않고도 새 칸이 추가될 때마다 섬의 개수를 보고할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
지도를 한 칸씩 살펴보세요. 이전에 어떤 섬도 차지하지 않은 육지 칸에 도달했을 때, 새로운 섬을 몇 개 찾았나요?
새로운 섬을 찾으면, 그 섬과 연결된 모든 땅 칸을 방문하고 각각을 방문한 것으로 표시하여 스캔에서 같은 섬을 다시 세지 않도록 하세요.
아직 방문하지 않은 칸을 큐(너비 우선) 또는 명시적인 스택(깊이 우선)으로 탐색하세요. 거대한 하나의 섬으로 이루어진 지도에서는 재귀 검색이 호출 스택을 모두 소진할 수 있지만, 직접 만든 큐나 스택을 사용하는 반복문은 그렇지 않습니다.
풀이
각 육지 칸을 주변의 육지 칸과 연결된 노드로 취급하세요. 섬은 하나의 연결된 덩어리입니다. 지도를 훑다가 아직 보지 않은 육지에 도달할 때마다 새로운 섬으로 세고, 플러드 필을 수행해 그 섬의 모든 칸을 표시하세요. 그러면 훑는 동안 같은 섬을 다시 세지 않습니다.
명시적 스택을 사용한 플러드 필(DFS)
핵심 아이디어
표시되지 않은 육지 칸은 이미 개수를 센 섬에 속할 수 없습니다. 섬을 셀 때 섬 전체를 표시하기 때문입니다. 따라서 이 칸은 새로운 섬에서 시작합니다. 직접 관리하는 스택이 나머지를 표시합니다. 꺼낸 각 칸은 표시되지 않은 육지 이웃 칸을 스택에 추가하고, 스택이 비면 섬 전체가 표시된 것입니다.
직접 관리하는 스택이 중요한 이유는 150 × 150 크기의 온통 육지인 지도에서 재귀적 채우기가 22,500번까지 깊어질 수 있기 때문입니다. 각 칸은 최대 한 번 스택에 추가되고 네 이웃을 확인하므로, 시간 복잡도는 O(rows × cols)입니다. 지도가 온통 육지라면 표시와 스택에 O(rows × cols) 공간이 필요합니다.
알고리즘
- 모든 칸에 방문 표시를 만들고 count를 0으로 설정합니다.
- 물을 건너뛰고 이미 방문한 칸을 제외하면서 모든 칸을 검사합니다.
- 방문하지 않은 육지를 발견하면 count에 1을 더하고, 해당 칸을 표시한 다음 스택에 넣습니다.
- 스택이 빌 때까지 칸을 꺼내고, 맵 안에 있는 방문하지 않은 육지인 각 이웃 칸을 표시한 뒤 스택에 넣습니다.
- 검사가 끝나면 count를 반환합니다.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
# Land that no island has claimed yet: a new island.
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
# Mark on push, so no square enters the stack twice.
seen[ni][nj] = True
stack.append((ni, nj))
return count큐를 사용한 플러드 필(fill) (BFS)
핵심 아이디어
개수는 같은 방식으로 계산되며, 방문 순서만 달라집니다. 큐는 앞에서 칸을 꺼내고 표시되지 않은 인접 육지를 뒤에 추가하므로, 섬을 고리 형태로 방문합니다. 먼저 첫 번째 칸을 방문하고, 그다음 한 칸 떨어진 모든 칸을, 이어서 두 칸 떨어진 모든 칸을 방문합니다. 모든 칸은 여전히 한 번씩 방문하며, 시간과 공간 복잡도는 O(rows × cols)입니다.
고리 순서를 통해 각 칸의 시작점으로부터의 거리를 알 수 있으므로, 각 칸에 숫자 하나만 추가하면 같은 반복문으로 격자에서 최단 경로 문제에 답할 수 있습니다.
알고리즘
- 모든 칸에 방문 표시를 만들고 개수를 0으로 설정합니다.
- 모든 칸을 살펴보며, 물과 이미 방문한 칸은 건너뜁니다.
- 방문하지 않은 땅을 만나면 개수에 1을 더하고, 해당 칸에 표시한 다음 빈 큐에 넣습니다.
- 큐에 칸이 있는 동안 맨 앞에서 하나를 꺼내고, 지도 안에 있는 이웃 중 방문하지 않은 땅을 각각 맨 뒤에 추가하면서 추가할 때 표시합니다.
- 탐색이 끝나면 개수를 반환합니다.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
seen[ni][nj] = True
stack.append((ni, nj))
return count
함정과 경계 사례
- 칸을 스택이나 큐에 넣을 때가 아니라 꺼낼 때 표시하는 것. 그러면 같은 칸이 여러 번 들어갑니다.
- 칸을 문자
'1'이 아니라 숫자 1과 비교하는 것. 각 행은 문자열이므로 각 칸은 문자입니다. 0 ≤ row < rows와0 ≤ col < cols인지 확인하기 전에 이웃 칸을 읽는 것. 그러면 가장자리에 있는 육지 칸에서 지도 밖을 읽게 됩니다.- 채우기를 재귀적으로 작성하는 것. Python은 기본적으로 1,000회 호출에서 중단되며, 다른 언어에서는 큰 섬 하나를 처리할 때 스택 오버플로가 발생할 수 있습니다.
pop(0)으로 Python 리스트의 앞부분을 꺼내는 것. 이 연산은 리스트 길이에 비례하는 시간이 듭니다.collections.deque와popleft()를 사용하세요.
자주 묻는 질문4
Number of Islands의 시간 복잡도는 얼마인가요?
O(rows × cols). 탐색은 각 칸을 한 번씩 살펴보고, 각 육지 칸은 스택이나 큐에 한 번 들어가며 네 개의 이웃을 확인합니다. 방문 표시와 스택 또는 큐는 모든 칸이 육지인 지도에서 O(rows × cols)의 공간을 사용합니다.
섬의 개수를 구할 때 BFS와 DFS 중 어떤 것을 사용해야 할까요?
둘 다 같은 시간 및 공간 복잡도에서 올바릅니다. 개수 세기에는 섬의 모든 칸을 표시하기만 하면 되기 때문입니다. 큐를 사용하는 BFS는 재귀하지 않으며, DFS도 명시적인 스택을 사용하면 안전합니다.
유니온 파인드로 Number of Islands 문제를 풀 수 있나요?
네. 각 육지 칸을 각각 별도의 집합에 넣고, 육지 칸의 개수로 카운트를 시작하세요. 서로 이웃한 육지 칸을 쌍으로 합치고, 합치기로 서로 다른 두 집합이 연결될 때마다 카운트를 1씩 줄이세요. 경로 압축을 사용하면 시간 복잡도는 O(rows × cols)에 가깝습니다.
별도의 방문 배열 없이 섬의 개수를 셀 수 있나요?
네, 지도를 변경해도 된다면 가능합니다. 각 육지 칸에 도달하는 즉시 물로 바꾸세요. 많은 언어에서는 문자열을 제자리에서 변경할 수 없으므로, 먼저 행을 문자 격자에 복사해야 하며, 이때 방문 표시와 같은 공간이 듭니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def numIslands(grid):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
인자
grid = ["11000", "11000", "00100", "00011"]
예상 출력
3