모든 시작점의 거리를 0으로 놓아요
앞 BFS는 출발점 하나에서 끝까지의 거리를 구했어요. 이번에는 여러 칸에서 같은 시각에 시작해요. 시작점들을 모두 거리 0으로 큐에 넣으면 어느 시작점에서든 가장 빨리 도착한 시간이 기록돼요.
시작점 A·B 중 A를 끝까지 처리하고 나중에 B를 시작하면 동시에 퍼진다는 계약과 달라요. 출발 시각이 같은 모든 시작점을 먼저 모아요.
하루에 퍼지는 칸들을 같은 거리로 읽어요
격자 {{1,0,0},{0,-1,0},{0,0,1}}에서 두 1이 시작점이고 −1은 벽이에요.
| 시각 | 새로 도착하는 칸 |
|---|---|
| 0 | (0,0), (2,2) |
| 1 | (0,1), (1,0), (1,2), (2,1) |
| 2 | (0,2), (2,0) |
마지막 대상이 2일에 채워져 전체 완료는 2예요. 벽은 채울 대상이 아니에요. 시작점이 없는데 0인 대상이 있다면 전파를 시작할 수 없어요. 원래 채울 대상이 하나도 없다면 기다릴 시간이 없어요.
직접 풀어봐요
grid의 1은 처음 활성화된 칸, 0은 아직 활성화되지 않은 칸, −1은 벽이에요. 매일 현재 활성 칸에서 상하좌우의 0인 칸으로 동시에 퍼져요. 모든 0이 활성화되는 최소 날짜 수를 반환하고, 못 채우는 0이 있으면 −1을 반환해요. 처음부터 0인 칸이 없으면 0을 반환해요.
행·열 수는 각각 1~15이고 모든 행의 길이는 같아요. 값은 −1·0·1만 있어요. 실행용 입력은 rows cols와 격자 값들이고 출력은 반환값이에요. 하네스가 입출력을 처리해요.
예시 1: grid={{1,0,0},{0,-1,0},{0,0,1}} → 2. 두 시작점에서 동시에 퍼져 마지막 칸들이 2일에 채워져요.
예시 2: grid={{1,-1,0},{0,-1,0}} → -1. 벽 오른쪽의 0에는 도달할 수 없어요.
예시 입력
3 3 1 0 0 0 -1 0 0 0 1
예상 결과
2
예시 입력
2 3 1 -1 0 0 -1 0
예상 결과
-1
핵심 개념
bfs-grid: 모든 시작점을 같은 거리 0으로 넣고 마지막 완료를 읽어요.