두 바다로 흐르는 빗물
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
직사각형 모양의 섬을 칸으로 나눈 지도 heights가 주어집니다. heights[i][j]는 그 칸의 높이입니다.
섬의 위쪽과 왼쪽 해안은 북서해에, 아래쪽과 오른쪽 해안은 남동해에 맞닿아 있습니다.
어떤 칸에 비가 내리면 빗물은 상하좌우로 이웃한 칸 중 높이가 현재 칸 이하인 칸으로 흘러갈 수 있습니다. 바다에 맞닿은 가장자리 칸의 빗물은 그 바다로 흘러 들어갑니다. (맨 위 행의 칸은 북서해에, 맨 오른쪽 열의 칸은 남동해에 맞닿는 식입니다.)
빗물이 북서해와 남동해 양쪽 모두에 닿을 수 있는 칸의 개수를 반환하세요. 빗물은 갈림길에서 여러 갈래로 나뉘어 흐를 수 있다고 봅니다.
입출력 예
| heights | result |
|---|---|
[[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]] | 7 |
[[3, 3, 3], [3, 1, 3], [3, 3, 3]] | 8 |
[[7]] | 1 |
입출력 예 설명
예 1 — 양쪽 바다에 닿는 칸은 (0,4), (1,3), (1,4), (2,2), (3,0), (3,1), (4,0) 일곱 개입니다.
예를 들어 높이 5인 (2,2)의 빗물은 (1,2) → (0,2)를 거쳐 북서해로, (2,3) → (2,4)를 거쳐 남동해로 흐릅니다.
예 2 — 가운데 칸은 사방이 더 높아 물이 고입니다. 가장자리 8칸은 같은 높이의 해안을 따라 양쪽 바다에 닿습니다.
예 3 — 한 칸짜리 섬은 네 해안 모두에 맞닿아 있습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(heights: int[][]) → int
제한 사항
-
heights.length -
heights[i].length, 모든 행의 길이는 같습니다. -
heights[i][j]
기대 복잡도
- 시간
- O(HW)
- 공간
- O(HW)
입출력 예
| heights | 기대 출력 |
|---|---|
[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] | 7 |
[[3,3,3],[3,1,3],[3,3,3]] | 8 |
[[7]] | 1 |
힌트
힌트
칸마다 빗물을 따라가 보는 탐색을 하면 칸 하나에 최대 , 전체 이 되어 시간 초과가 납니다.
거꾸로 생각해 보세요. "이 칸에서 바다로 갈 수 있는가"는 "바다에서 출발해 높이가 같거나 높아지는 방향으로만 거슬러 올라가 이 칸에 닿는가"와 같습니다.
- 위쪽 행과 왼쪽 열의 칸을 모두 시작점으로 BFS/DFS를 해서, 이웃의 높이가 현재 칸 이상일 때만 넘어갑니다. 닿은 칸이 북서해로 흐를 수 있는 칸입니다.
- 아래쪽 행과 오른쪽 열에서 같은 탐색을 해 남동해로 흐를 수 있는 칸을 구합니다.
- 두 탐색에서 모두 표시된 칸의 개수가 답입니다.
격자가 최대 25만 칸이므로 재귀 대신 큐나 명시적 스택을 쓰는 것이 안전합니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1108 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 5 | 판정만 |