Funcia
Lv.2bfsgraphgrid

곰팡이가 번지는 시간

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

창고 바닥이 격자 grid로 주어집니다. 각 칸의 값은 다음 중 하나입니다.

  • 1: 곰팡이가 핀 칸
  • 0: 깨끗한 칸
  • -1: 벽 (곰팡이가 번지지 않습니다)

1분이 지날 때마다, 곰팡이가 핀 칸과 상하좌우로 맞닿은 깨끗한 칸에 곰팡이가 번집니다.

모든 깨끗한 칸에 곰팡이가 피기까지 걸리는 **최소 시간(분)**을 반환하세요. 끝까지 곰팡이가 닿지 않는 깨끗한 칸이 있으면 -1을, 처음부터 깨끗한 칸이 없으면 0을 반환합니다.

입출력 예

gridresult
[[1, 0, 0], [0, -1, 0], [0, 0, 0]]4
[[1, -1, 0], [0, -1, 0]]-1
[[1, 0, 1], [0, 0, 0]]2

입출력 예 설명

예 1 — 왼쪽 위에서 출발해 가운데 벽을 돌아 오른쪽 아래 칸에 닿는 데 4분이 걸립니다.

예 2 — 오른쪽 열은 벽으로 막혀 곰팡이가 닿지 않습니다.

예 3 — 곰팡이가 두 군데서 동시에 번집니다. 아래 줄 가운데 칸이 2분째에 마지막으로 물듭니다.

효율성

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

함수 시그니처

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

제한 사항

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

기대 복잡도

시간
O(HW)
공간
O(HW)

입출력 예

grid기대 출력
[[1,0,0],[0,-1,0],[0,0,0]]4
[[1,-1,0],[0,-1,0]]-1
[[1,0,1],[0,0,0]]2

힌트

힌트

곰팡이가 핀 모든 칸을 처음부터 큐에 넣고 BFS를 한 번만 돌리세요(다중 출발점 BFS).

  • 시작 칸들의 거리는 0입니다.
  • 큐에서 꺼낸 칸의 이웃 중 깨끗한 칸은 거리 d + 1로 표시하고 큐에 넣습니다.
  • BFS가 끝난 뒤 깨끗한 칸이 남아 있으면 -1, 아니면 가장 큰 거리가 답입니다.

출발점마다 따로 BFS를 돌리면 출발점 수만큼 느려집니다. 동시에 퍼지는 상황은 "거리 0인 칸이 여러 개인 BFS" 하나로 표현됩니다.

칸이 25만 개라 재귀 DFS는 쓰지 마세요. 그리고 거리 순서가 중요한 문제라 DFS로는 애초에 답을 구할 수 없습니다.

복잡도 목표

1분마다 격자 전체를 훑으며 번지는 칸을 찾는 시뮬레이션은 O(HW⋅T)O(HW \cdot T)입니다. 구불구불한 통로에서는 TT가 HW/2HW/2 가까이 되어 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

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

테스트 그룹

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

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