N×M 크기의 이진 행렬(binary matrix)이 주어졌다고 가정해 보겠습니다. 여기서 0은 빈 칸을, 1은 막힌 칸(장애물)을 의미합니다. 행렬의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리에 도달할 수 있는 경로의 수를 구하는 것이 목표입니다. 단, 이동은 오른쪽 또는 아래 방향으로만 가능하며, 답이 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 반환해야 합니다.
예를 들어 입력이 다음과 같다면
| 0 | 0 | 1 |
| 0 | 0 | 0 |
| 1 | 1 | 0 |
출력은 2가 됩니다. 오른쪽 아래에 도달할 수 있는 두 가지 경로는 [오른쪽, 아래, 오른쪽, 아래]와 [아래, 오른쪽, 오른쪽, 아래]입니다.
풀이 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 각 칸에 도달할 수 있는 경로의 수를 저장하는 DP 테이블을 만들고, 현재 칸의 값은 '위쪽 칸의 값 + 왼쪽 칸의 값'으로 계산합니다. 구체적인 절차는 다음과 같습니다.
- 주어진 행렬과 같은 크기의 DP 테이블(dp)을 생성하고 모든 값을 0으로 초기화합니다.
- dp[0, 0] := 1로 설정합니다(시작 지점).
- 첫 번째 열을 채웁니다: matrix[i, 0]이 1이면 반복문을 종료하고, 그렇지 않으면 dp[i, 0] := 1로 설정합니다.
- 첫 번째 행을 채웁니다: matrix[0, j]가 1이면 반복문을 종료하고, 그렇지 않으면 dp[0, j] := 1로 설정합니다.
- 나머지 칸을 순회합니다: matrix[i, j]가 1이면 dp[i, j] := 0으로 설정하고, 그렇지 않으면 dp[i, j] := dp[i-1, j] + dp[i, j-1]로 계산합니다.
- 마지막으로 DP 테이블의 오른쪽 아래 값을 반환합니다.
파이썬 구현 예제
다음 구현 예제를 통해 더 자세히 이해해 보겠습니다.
class Solution: def solve(self, matrix): dp = [[0] * len(matrix[0]) for _ in range(len(matrix))] dp[0][0] = 1 for i in range(1, len(matrix)): if matrix[i][0] == 1: break else: dp[i][0] = 1 for j in range(1, len(matrix[0])): if matrix[0][j] == 1: break else: dp[0][j] = 1 for i in range(1, len(matrix)): for j in range(1, len(matrix[0])): if matrix[i][j] == 1: dp[i][j] = 0 else: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[-1][-1] ob = Solution() matrix = [ [0, 0, 1], [0, 0, 0], [1, 1, 0] ] print(ob.solve(matrix))
입력
matrix = [ [0, 0, 1], [0, 0, 0], [1, 1, 0] ]
출력
2
복잡도 분석
행렬의 모든 칸을 한 번씩만 방문하므로 시간 복잡도는 O(N×M)입니다. DP 테이블을 위해 N×M 크기의 추가 공간을 사용하므로 공간 복잡도 역시 O(N×M)입니다. 장애물이 있는 칸은 경로의 수를 0으로 처리하기 때문에, 해당 칸을 지나는 모든 경로가 자연스럽게 제외됩니다.