최단 이동 경로의 개수

가장 짧은 거리와 그 방법 수는 달라요

앞 BFS는 최소 날짜를 반환했어요. 이번에는 같은 최단거리로 도착하는 경로가 여러 개일 때 그 개수를 세요. 벽 없는 2×2에서 끝까지 거리는 2지만 이동 순서는 오른쪽→아래, 아래→오른쪽 두 개예요.

dist에는 최단거리를, ways에는 그 거리로 도달하는 경로 수를 따로 담아요. 시작 칸은 거리 0이고 아무 이동 없이 그곳에 있는 경로 하나로 시작해요.

같은 거리로 오는 다른 후보는 더해요

어떤 칸의 최단거리가 3으로 처음 정해졌다고 해요. 다른 이웃에서 거리 2까지 온 경로는 한 번 더 이동해 같은 최단거리 3을 만들 수 있어요. 그 경로 수는 더해요. 거리 4 이상으로 들어오는 경우는 최단경로가 아니므로 세지 않아요.

방문했다는 이유만으로 모든 재도착을 건너뛰면 같은 길이의 다른 경로를 잃어요. 경로 수는 커질 수 있어 1,000,000,007로 나눈 나머지를 유지해요. 이 단계는 앞 BFS의 거리 기록에 ‘동률 후보 수’라는 상태를 추가해요.

직접 풀어봐요

grid의 0은 통과 가능한 칸, 1은 벽이에요. (0,0)에서 (rows−1,cols−1)까지 상하좌우로 이동하는 최단경로 개수를 1,000,000,007로 나눈 나머지로 반환해요. 이동 순서의 좌표 목록이 다르면 다른 경로예요. 도달 불가면 0, 1×1이면 이동하지 않는 경로 하나라 1이에요.

행·열 수는 각각 1~15이고 모든 행의 길이는 같아요. 시작과 끝은 항상 0이에요. 실행용 입력은 rows cols와 격자 값들, 출력은 반환값이에요. 하네스가 입출력을 처리해요.

예시 1: grid={{0,0},{0,0}} → 2. 오른쪽→아래와 아래→오른쪽 두 최단경로예요. 예시 2: grid={{0,0,0},{0,1,0},{0,0,0}} → 2. 중앙 벽을 위쪽 또는 왼쪽 둘레로 돌아가는 두 최단경로예요.

2 2
0 0
0 0

2

3 3
0 0 0
0 1 0
0 0 0

2