문제 소개
세 가지 값 중 하나를 가지는 2차원 행렬(격자)이 주어졌다고 가정해 보겠습니다.
- 0 : 빈 셀
- 1 : 동전이 있는 셀
- -1 : 벽(지나갈 수 없는 셀)
왼쪽 상단 셀에서 출발해 오른쪽 또는 아래 방향으로만 이동하여 오른쪽 하단 셀에 도달한 뒤, 다시 위쪽 또는 왼쪽 방향으로만 이동하여 시작 지점으로 돌아와야 합니다. 이때 동전을 주우면 해당 셀의 값은 0으로 바뀌므로, 같은 동전을 두 번 모을 수 없습니다. 만약 오른쪽 하단 셀에 도달할 수 없다면 0을 반환해야 합니다.
예시 입력
| 0 | 1 | 1 |
| 1 | 1 | 1 |
| -1 | 1 | 1 |
| 0 | 1 | 1 |
이 경우 출력값은 8입니다.
풀이 접근 방식
이 문제의 핵심은 왕복 경로를 두 명의 사람이 동시에 출발점에서 도착점으로 이동하는 경로로 치환하는 것입니다. 가는 길과 오는 길을 각각 따로 계산하면 동전이 이미 수거된 상태를 반영하기 어렵지만, 두 경로를 동시에 진행한다고 생각하면 각 단계에서 두 위치의 상태를 함께 고려할 수 있습니다.
구체적인 해결 절차는 다음과 같습니다.
- n := 행렬의 행 개수, m := 열 개수로 설정합니다.
- 네 개의 매개변수 (i, j, k, l)를 받는 util() 함수를 정의합니다. 여기서 (i, j)는 첫 번째 경로의 현재 위치, (k, l)은 두 번째 경로의 현재 위치를 나타냅니다.
- (i, j)가 행렬 범위를 벗어나거나 mat[i][j]가 -1이면 -inf를 반환합니다.
- (k, l)도 마찬가지로 범위를 벗어나거나 벽이면 -inf를 반환합니다.
- i, j, k, l이 모두 0이면(출발점) mat[0][0]을 반환합니다.
- best := -inf로 초기화한 뒤, 각 경로마다 가능한 이동 방향인 (-1, 0), (0, -1)의 조합을 모두 시도하며 best를 최댓값으로 갱신합니다.
- 마지막으로 mat[i][j]에 더하고, i와 k가 다른 경우에만(즉 두 경로가 같은 셀에 있지 않은 경우에만) mat[k][l]을 추가로 더한 값을 반환합니다. 이렇게 하면 같은 셀의 동전이 중복해서 계산되는 것을 방지할 수 있습니다.
- 메인 함수에서는 max(0, util(n-1, m-1, n-1, m-1))을 반환합니다. 도달할 수 없는 경우 음수가 나오기 때문에 0과 비교하여 처리합니다.
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
구현 예시
class Solution: def solve(self, mat): n, m = len(mat), len(mat[0]) def util(i, j, k, l): if not (0 <= i < n and 0 <= j < m) or mat[i][j] == -1: return -1e9 if not (0 <= k < n and 0 <= l < m) or mat[k][l] == -1: return -1e9 if i == 0 and j == 0 and k == 0 and l == 0: return mat[0][0] best = -1e9 for dx1, dy1 in [(-1, 0), (0, -1)]: for dx2, dy2 in [(-1, 0), (0, -1)]: best = max(best, util(i + dy1, j + dx1, k + dy2, l + dx2)) return mat[i][j] + (i != k) * mat[k][l] + best return max(0, util(n - 1, m - 1, n - 1, m - 1)) ob = Solution() matrix = [ [0, 1, 1], [1, 1, 1], [1, -1, 1], [0, 1, 1] ] print(ob.solve(matrix))
입력
[ [0, 1, 1], [1, 1, 1], [1, -1, 1], [0, 1, 1] ]
출력
8
정리
이 문제는 단순히 두 경로를 따로 계산하면 해결할 수 없으며, 두 경로를 동시에 시뮬레이션하면서 같은 셀에 있는 경우 동전을 한 번만 세도록 처리하는 것이 핵심입니다. 재귀 호출을 통해 네 개의 좌표를 관리하고, 범위 밖이나 벽을 만나면 유효하지 않은 값(-1e9)을 반환함으로써 자연스럽게 불가능한 경로를 걸러낼 수 있습니다.