문제 설명
2차원 행렬이 주어지고, 각 셀 matrix[r][c]에는 해당 위치에 놓인 동전의 개수가 저장되어 있다고 가정해 봅시다. 우리는 행렬의 아무 위치에서나 출발하여 상하좌우 네 방향으로만 이동하면서(대각선 이동은 불가) 동전을 최대한 많이 모으려고 합니다.
단, 다음 규칙이 적용됩니다.
- 어떤 셀에 도착하면 그 셀의 동전을 모두 수집하고, 해당 셀의 값은 0이 됩니다.
- 동전이 0개인 셀은 방문할 수 없습니다.
- 목표는 수집할 수 있는 동전의 최대 개수를 구하는 것입니다.
예시
입력 행렬이 다음과 같다면,
| 2 | 4 | 3 |
| 3 | 6 | 0 |
| 2 | 0 | 12 |
출력은 18이 됩니다. 경로 2 → 3 → 6 → 4 → 3을 따라 이동하면 총 18개의 동전을 수집할 수 있기 때문입니다.
접근 방법: 백트래킹 DFS
이 문제는 백트래킹(backtracking)을 활용한 깊이 우선 탐색(DFS)으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 행렬이 비어 있으면 0을 반환합니다.
- n := 행렬의 행 개수, m := 열 개수로 설정합니다.
- 방향 배열 x := [-1, 1, 0, 0], y := [0, 0, -1, 1]을 정의합니다(상, 하, 좌, 우).
- util(a, b) 함수를 정의합니다. 현재 위치 (a, b)에서 출발했을 때 수집할 수 있는 최대 동전 수를 반환합니다.
- ret := 0으로 초기화합니다.
- k를 0부터 3까지 반복하며 인접 셀 (t1, t2) = (x[k] + a, y[k] + b)를 확인합니다.
- (t1, t2)가 유효한 셀이라면(범위 내에 있고 동전이 있는 경우):
- t := mat[t1][t2] 값을 임시 저장하고, mat[t1][t2] := 0으로 만들어 방문 처리합니다.
- ret := ret와 util(t1, t2) + t 중 더 큰 값으로 갱신합니다.
- mat[t1][t2] := t로 되돌려 놓아 상태를 복원합니다(백트래킹).
- 모든 방향 탐색이 끝나면 ret을 반환합니다.
- 메인 로직에서는 res := 0으로 초기화한 뒤, 행렬의 모든 셀 (i, j)를 순회하면서 동전이 있는 셀에서 출발해 util(i, j) + temp의 최댓값을 res에 저장하고, 마지막에 res를 반환합니다.
구현 예제
class Solution:
def solve(self, mat):
if not mat:
return 0
n, m = len(mat), len(mat[0])
x, y = [-1, 1, 0, 0], [0, 0, -1, 1]
def ok(a, b):
return 0 <= a < n and 0 <= b < m and mat[a][b]
def util(a, b):
ret = 0
for k in range(4):
t1, t2 = x[k] + a, y[k] + b
if ok(t1, t2):
t, mat[t1][t2] = mat[t1][t2], 0
ret = max(ret, util(t1, t2) + t)
mat[t1][t2] = t
return ret
res = 0
for i in range(n):
for j in range(m):
if mat[i][j]:
temp, mat[i][j] = mat[i][j], 0
res = max(res, util(i, j) + temp)
return res
ob = Solution()
matrix = [
[2, 4, 3],
[3, 6, 0],
[2, 0, 12]
]
print(ob.solve(matrix))입력
[ [2, 4, 3], [3, 6, 0], [2, 0, 12] ]
출력
18
복잡도 분석
백트래킹 기반 완전 탐색이므로 시간 복잡도는 지수적으로 증가하며, 대략 O(4^(n×m)) 수준입니다. 공간 복잡도는 재귀 호출 스택 때문에 O(n×m)입니다. 따라서 이 접근법은 행렬의 크기가 작은 경우에 적합하며, 큰 입력에는 메모이제이션 등의 최적화가 필요할 수 있습니다.