Lv.2bfsdfsgraphgrid
섬의 개수
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
0(바다)과 1(땅)로 이루어진 2차원 배열 grid가 주어집니다.
상하좌우로 이어진 땅을 하나의 섬이라고 할 때, 섬의 개수를 반환하세요. 대각선은 이어진 것으로 보지 않습니다.
입출력 예
| grid | result |
|---|---|
[[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
- , (
grid는 직사각형) grid[i][j]는0또는1
Expected complexity
- Time
- O(H*W)
- Space
- O(H*W)
Examples
| grid | Expected |
|---|---|
[[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개입니다. 각 칸을 한 번씩만 방문하는 풀이가 필요합니다.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1400 ms | estimated |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1000 ms | derived |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 4 | verdict only |