Funcia
Lv.2bfsdfsgraphgrid

섬의 개수

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

0(바다)과 1(땅)로 이루어진 2차원 배열 grid가 주어집니다.

상하좌우로 이어진 땅을 하나의 섬이라고 할 때, 섬의 개수를 반환하세요. 대각선은 이어진 것으로 보지 않습니다.

입출력 예

gridresult
[[1,1,0,0],[1,1,0,0],[0,0,1,0],[0,0,0,1]]3
[[1,0,1],[0,1,0],[1,0,1]]5
[[0,0],[0,0]]0

입출력 예 설명

예 1 — 왼쪽 위 2×2 덩어리, 가운데 한 칸, 오른쪽 아래 한 칸으로 3개입니다.

예 2 — 대각선은 이어지지 않으므로 다섯 칸이 각각 섬입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

Function signature

solution(grid: int[][]) → int

Constraints

  • 1≤H≤5001 \le H \le 500, 1≤W≤5001 \le W \le 500 (grid는 H×WH \times W 직사각형)
  • grid[i][j] 는 0 또는 1

Expected complexity

Time
O(H*W)
Space
O(H*W)

Examples

gridExpected
[[1,1,0,0],[1,1,0,0],[0,0,1,0],[0,0,0,1]]3
[[1,0,1],[0,1,0],[1,0,1]]5
[[0,0],[0,0]]0

Hint

Hint

모든 칸을 순회하다가 아직 방문하지 않은 땅을 만나면 섬 하나를 새로 발견한 것이니 카운트를 올리고, 거기서부터 이어진 땅을 전부 방문 처리합니다.

이어진 땅을 훑는 것은 큐를 쓰든 스택을 쓰든 됩니다. 다만 칸이 25만 개라 재귀는 스택 오버플로우 위험이 있습니다. 한 줄로 이어진 땅이면 재귀 깊이가 25만이 되기 때문입니다. 큐를 쓰는 편이 안전합니다.

큐를 쓸 때 반드시 지킬 것이 하나 있습니다. 큐에 넣는 순간 방문 처리하세요. 꺼낼 때 처리하면 같은 칸이 큐에 여러 번 들어가 메모리와 시간을 낭비합니다.

방향은 배열로 두면 짧습니다.

int[] dy = { -1, 1, 0, 0 };
int[] dx = { 0, 0, -1, 1 };

복잡도 목표

칸 수가 최대 250,000개입니다. 각 칸을 한 번씩만 방문하는 O(HW)O(HW) 풀이가 필요합니다.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251400 msestimated
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1000 msderived

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.