문제 개요
2차원 이진 행렬과 하나의 값 k가 주어진 상황을 생각해 봅시다. 왼쪽 위(시작 셀)에서 출발하여 오른쪽 아래(도착 셀)까지 이동해야 하며, 한 번의 이동으로는 아래(D) 또는 오른쪽(R) 방향으로만 움직일 수 있습니다.
경로의 점수는 해당 경로가 지나가는 모든 셀의 값을 합한 것으로 정의됩니다. 우리가 구해야 할 것은 점수가 정확히 k가 되는 경로의 개수입니다. 가능한 경로의 수가 기하급수적으로 늘어날 수 있기 때문에, 결과는 10^9 + 7로 나눈 나머지를 반환해야 합니다.
입력 예시
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 0 |
K = 2일 때 출력은 4입니다. 점수가 2가 되는 경로는 [R,R,D,D], [D,R,R,D], [D,D,R,R], [D,R,D,R] 네 가지입니다. 여기서 D는 아래 이동, R은 오른쪽 이동을 의미합니다.
풀이 접근 방식
이 문제는 DFS(깊이 우선 탐색) 재귀 호출을 활용하면 직관적으로 해결할 수 있습니다. 각 단계는 다음과 같습니다.
- 나머지 연산에 사용할 값 deno := 10^9 + 7로 설정
- m := 행렬의 행 개수, n := 행렬의 열 개수
- dfs() 함수를 정의 (매개변수: i, j, pts)
- i >= m 또는 j >= n이면 0을 반환 (범위를 벗어난 경우)
- pts := pts + matrix[i, j]로 현재 셀의 값을 누적
- i == m - 1이고 j == n - 1이면(도착 셀 도달), pts == k일 때 1, 아니면 0을 반환
- 그 외의 경우 dfs(i + 1, j, pts) + dfs(i, j + 1, pts)를 반환
- 메인에서 dfs(0, 0, 0) mod deno를 최종 반환
구현 예제
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution: def solve(self, matrix, k): m, n = len(matrix), len(matrix[0]) def dfs(i=0, j=0, pts=0): if i >= m or j >= n: return 0 pts += matrix[i][j] if i == m - 1 and j == n - 1: return int(pts == k) return dfs(i + 1, j, pts) + dfs(i, j + 1, pts) return dfs() % (10 ** 9 + 7) ob = Solution() matrix = [ [0, 0, 1], [1, 0, 1], [0, 1, 0] ] k = 2 print(ob.solve(matrix, k))
입력
[ [0, 0, 1], [1, 0, 1], [0, 1, 0] ], 2
출력
4
참고: 성능 개선 팁
위 단순 재귀 구현은 시간 복잡도가 O(2^(m+n))으로 지수적으로 증가합니다. 행렬의 크기가 커지면 메모이제이션(memoization)을 적용하여 (i, j, pts) 상태별 결과를 캐싱하는 것이 좋습니다. 또한 pts 대신 "목표 점수까지 남은 값"을 상태로 관리하면 동적 계획법(DP)으로 전환하기도 수월합니다.