Funcia
Lv.2bfsdfsgraphgrid

두 바다로 흐르는 빗물

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

직사각형 모양의 섬을 H×WH \times W 칸으로 나눈 지도 heights가 주어집니다. heights[i][j]는 그 칸의 높이입니다. 섬의 위쪽과 왼쪽 해안은 북서해에, 아래쪽과 오른쪽 해안은 남동해에 맞닿아 있습니다.

어떤 칸에 비가 내리면 빗물은 상하좌우로 이웃한 칸 중 높이가 현재 칸 이하인 칸으로 흘러갈 수 있습니다. 바다에 맞닿은 가장자리 칸의 빗물은 그 바다로 흘러 들어갑니다. (맨 위 행의 칸은 북서해에, 맨 오른쪽 열의 칸은 남동해에 맞닿는 식입니다.)

빗물이 북서해와 남동해 양쪽 모두에 닿을 수 있는 칸의 개수를 반환하세요. 빗물은 갈림길에서 여러 갈래로 나뉘어 흐를 수 있다고 봅니다.

입출력 예

heightsresult
[[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

제한 사항

  • 1≤H=1 \le H = heights.length ≤500\le 500
  • 1≤W=1 \le W = heights[i].length ≤500\le 500, 모든 행의 길이는 같습니다.
  • 0≤0 \le heights[i][j] ≤109\le 10^9

기대 복잡도

시간
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

힌트

힌트

칸마다 빗물을 따라가 보는 탐색을 하면 칸 하나에 최대 O(HW)O(HW), 전체 O((HW)2)O((HW)^2)이 되어 시간 초과가 납니다.

거꾸로 생각해 보세요. "이 칸에서 바다로 갈 수 있는가"는 "바다에서 출발해 높이가 같거나 높아지는 방향으로만 거슬러 올라가 이 칸에 닿는가"와 같습니다.

  1. 위쪽 행과 왼쪽 열의 칸을 모두 시작점으로 BFS/DFS를 해서, 이웃의 높이가 현재 칸 이상일 때만 넘어갑니다. 닿은 칸이 북서해로 흐를 수 있는 칸입니다.
  2. 아래쪽 행과 오른쪽 열에서 같은 탐색을 해 남동해로 흐를 수 있는 칸을 구합니다.
  3. 두 탐색에서 모두 표시된 칸의 개수가 답입니다.

격자가 최대 25만 칸이므로 재귀 대신 큐나 명시적 스택을 쓰는 것이 안전합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251108 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance605판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.