Longest Increasing Path in a Matrix
m개의 행과 n개의 열로 이루어진 정수 격자인 matrix를 행의 리스트로 받습니다. 경로는 위, 아래, 왼쪽 또는 오른쪽으로 이동하며(대각선 이동이나 가장자리에서 반대편으로 이어지는 이동은 불가), 이동할 때마다 반드시 이전보다 엄격히 큰 값의 셀에 도착해야 합니다. 이러한 경로 중 가장 긴 경로에 포함된 셀의 수를 반환하세요. 셀 하나도 길이가 1인 경로입니다.
함수
- matrixinteger-2d-array
- 길이가 모두 같은 행들의 목록으로 표현된 값의 격자
- 반환값integer
- 가장 긴 엄격히 증가하는 경로에 있는 셀의 수
제약 조건
1 ≤ m, n ≤ 100, 여기서m = matrix.length이고n = matrix[i].length입니다.- 모든 행의 길이는
n으로 같습니다. 0 ≤ matrix[i][j] ≤ 231-1
예제
- 입력
- matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
- 출력
- 7
- 설명
- 경로 3, 4, 5, 6, 7, 8, 9는 오른쪽 열을 따라 아래로 내려가고, 맨 아래 행을 따라간 다음 가운데 열을 따라 위로 올라가 9에 도달합니다. 7개의 셀입니다. 가장 작은 값인 1에서 시작하는 최적의 경로는 5개의 셀로 이루어져 있습니다.
- 입력
- matrix = [[2, 2, 2], [2, 5, 2]]
- 출력
- 2
- 설명
- 같은 값은 한 단계 올라간 것이 아니므로, 어떤 경로도 2를 따라 이동하지 않습니다. 가장 좋은 경로는 5 주변에 있는 세 개의 2 중 하나에서 5로 이동하는 것입니다: 2칸.
- 입력
- matrix = [[4, 4], [4, 4], [4, 4]]
- 출력
- 1
- 설명
- 모든 값이 4이므로 어느 곳에서도 이동할 수 없습니다. 각 셀은 그 자체로 1개 셀의 경로이며, 정답은 1입니다.
후속 질문
가장 긴 경로 하나의 길이와 함께 해당 경로의 셀들도 반환할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
경로가 이미 방문한 셀로 다시 돌아올 수 있을까요? 경로를 따라가며 값이 어떻게 변하는지 살펴보세요.
값은 증가하기만 하므로 경로에서 같은 셀을 다시 지나지 않으며, 한 셀에서 시작하는 최장 경로는 그 셀에 어떻게 도달했는지에 영향을 받지 않습니다. 최장 경로의 길이는 그 셀보다 큰 이웃 중 가장 좋은 셀에서 시작하는 최장 경로에 1을 더한 값입니다.
각 셀마다 그 수를 한 번 계산해 저장하세요. 직접 만든 스택을 사용해 더 큰 이웃을 대상으로 깊이 우선 탐색을 수행하여 값을 채우거나, 격자의 봉우리부터 한 번에 한 층씩 제거하면서 층 수를 세세요.
풀이
각 셀에서 더 큰 이웃 셀마다 화살표를 그리세요. 모든 화살표를 따라가면 값이 커지므로, 화살표가 이어지는 경로는 순환할 수 없습니다. 따라서 이 격자는 방향 비순환 그래프이며, 답은 가장 긴 경로입니다. 순환이 없으면 한 셀에서 시작하는 가장 긴 경로는 그 셀에만 영향을 받으므로, 셀마다 한 번씩 계산하면 됩니다: O(m × n).
모든 증가 경로를 따르세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
모든 셀에서 경로를 시작하고 더 큰 이웃의 모든 분기를 따라 더 이상 이동할 곳이 없을 때까지 진행하세요. 가장 긴 경로가 정답입니다. 매 단계마다 값이 커지므로 경로가 같은 셀로 돌아오지 않으며 방문 집합도 필요하지 않습니다.
다른 경로가 어떤 셀을 지날 때마다 그 셀에서 시작하는 경로를 다시 계산합니다. 각 값이 행 번호와 열 번호의 합인 100 × 100 격자에서는 오른쪽이나 아래쪽으로 한 걸음 이동할 때마다 값이 커지며, 왼쪽 위 모서리에서 시작하는 경로는 10^58개가 넘습니다.
알고리즘
- 각 셀에 대해 (해당 셀, 1)을 스택에 넣습니다.
- (셀, 길이) 항목을 꺼내고 길이로 정답을 갱신합니다.
- 그리드 안에서 값이 엄격히 더 큰 각 이웃에 대해 (이웃, 길이 + 1)을 넣습니다.
- 스택이 빌 때까지 반복한 다음, 다음 시작 셀로 이동합니다.
- 지금까지 확인한 가장 큰 길이를 반환합니다.
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
answer = 0
for sr in range(rows):
for sc in range(cols):
# Each entry is one path in progress: the cell it ends on and
# how many cells it has.
stack = [(sr, sc, 1)]
while stack:
r, c, length = stack.pop()
answer = max(answer, length)
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
stack.append((nr, nc, length + 1))
return answer자신만의 스택을 사용한 메모이제이션 깊이 우선 탐색
핵심 아이디어
best[cell]를 그 셀에서 시작하는 가장 긴 증가 경로의 셀 개수라고 하자. 더 큰 이웃 nb에 대해 1 + max(best[nb])를 계산하고, 더 큰 이웃이 없으면 1이다. 경로에서 cell보다 앞에 있는 셀은 모두 더 작고 그 뒤에 올 수 없으므로 값을 저장해도 안전하다. 첫 번째 예시에서 9는 1, 8은 2, 7은 3, 6과 2는 4, 5와 1은 5, 4는 6, 3은 7을 얻는다.
경로가 10,000개의 셀을 모두 지날 수도 있어서 재귀를 사용하기에는 너무 깊으므로, 직접 스택을 관리하자. 맨 위 셀은 다음 방향을 시도하고, 아직 처리가 끝나지 않은 더 큰 이웃을 스택에 넣는다. 네 방향을 모두 시도하면 해당 셀을 꺼내고 best를 설정한다. "처리 중" 표시는 필요 없다. 스택의 각 셀은 그 아래 셀보다 크기 때문이다.
알고리즘
- 아직 알 수 없다는 의미로
best를 0으로 설정하고, 모든 셀의 방향 카운터를 0으로 설정합니다. best가 0인 각 셀을 스택에 넣습니다.- 맨 위의 셀에서 카운터를 증가시키고, 해당 이웃이 격자 안에 있으며 더 크고 아직 처리가 끝나지 않았다면 스택에 넣습니다.
- 네 방향을 모두 확인한 후 셀을 꺼내고, 더 큰 이웃들의
best중 가장 큰 값에 1을 더한 값으로best를 설정합니다. 그런 이웃이 없으면 1로 설정합니다. - 가장 큰
best를 반환합니다.
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
# best[r][c]: cells on the longest increasing path that starts at (r, c).
# 0 means not known yet.
best = [[0] * cols for _ in range(rows)]
# step[r][c]: how many of the 4 directions the search has tried from (r, c).
step = [[0] * cols for _ in range(rows)]
answer = 0
for sr in range(rows):
for sc in range(cols):
if best[sr][sc]:
continue
# Our own stack instead of recursion: a path can be thousands of
# cells long, past Python's limit of 1,000 nested calls.
stack = [(sr, sc)]
while stack:
r, c = stack[-1]
d = step[r][c]
if d < 4:
step[r][c] = d + 1
nr, nc = r + dirs[d][0], c + dirs[d][1]
# The stack only climbs, so a larger neighbour is never on it.
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c] and best[nr][nc] == 0:
stack.append((nr, nc))
continue
# Every larger neighbour is finished: build on the best of them.
stack.pop()
length = 1
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
length = max(length, best[nr][nc] + 1)
best[r][c] = length
answer = max(answer, length)
return answer격자의 꼭대기부터 벗겨 내기
핵심 아이디어
Kahn의 위상 정렬처럼 가장 큰 값부터 아래로 내려가며 같은 표를 만드세요. 봉우리, 즉 더 큰 이웃이 없는 셀은 길이가 1셀인 경로를 시작합니다. 이것이 레이어 1입니다. 모든 봉우리를 제거하면 마지막으로 더 큰 이웃을 잃은 셀들이 다음 레이어가 됩니다. 격자가 빌 때까지 반복하세요. 셀은 마지막 더 큰 이웃이 제거된 다음 라운드에 제거되므로, 그 레이어는 best와 같고 레이어 수가 답입니다. 첫 번째 예제의 레이어는 9, 8, 7, 2와 6, 1과 5, 4, 3입니다.
각 셀에 대해 남아 있는 더 큰 이웃의 수를 세세요. 셀을 제거하면 그보다 엄격히 작은 각 이웃의 수가 줄어들고, 수가 0이 된 셀은 다음 레이어에 들어갑니다. 각 셀은 한 번씩 제거됩니다. 따라서 시간 복잡도는 O(m × n)이며, 스택은 필요하지 않습니다.
알고리즘
- 모든 셀에 대해 값이 더 큰 이웃의 수를 센다.
- 개수가 0인 모든 셀을 현재 레이어에 넣는다.
- 레이어가 비어 있지 않은 동안 레이어 수에 1을 더한다. 레이어에 있는 각 셀에 대해 값이 엄격히 더 작은 각 이웃의 개수를 줄이고, 개수가 0이 된 이웃을 다음 레이어에 넣는다.
- 다음 레이어를 현재 레이어로 만들고 반복한다.
- 레이어 수를 반환한다.
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
# higher[r][c]: neighbours of (r, c) with a larger value, not peeled yet.
higher = [[0] * cols for _ in range(rows)]
layer = []
for r in range(rows):
for c in range(cols):
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
higher[r][c] += 1
# A peak: no neighbour is larger, so a path from it has one cell.
if higher[r][c] == 0:
layer.append((r, c))
layers = 0
while layer:
layers += 1
next_layer = []
for r, c in layer:
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
higher[nr][nc] -= 1
# Its last larger neighbour is peeled: it is a peak now.
if higher[nr][nc] == 0:
next_layer.append((nr, nc))
layer = next_layer
# Each layer is one step further from a peak; the count is the longest path.
return layers
함정과 경계 사례
>=대신>를 비교하는 경우. 서로 이웃한 4가 두 개 있으면 무차별 대입 방식은 영원히 앞뒤로 이동하고, 메모이제이션 검색은 아직 계산 중인 길이를 읽습니다.- Python에서 재귀를 사용하는 경우. 100 × 100 격자를 가로지르는 값들은 10,000개 셀로 이루어진 경로를 만들며, 이는 기본 한도인 1,000회 호출의 10배입니다.
- 플러드 필처럼 완료된 셀을 건너뛰는 경우. 저장된 길이가 바로 현재 셀에 필요한 값입니다.
- 가장 작은 값에서만 시작하는 경우. 첫 번째 예제에서 1은 5개의 셀을 만들지만, 정답인 7은 3에서 시작합니다.
- 길이를 0에서 시작하는 경우. 값이 모두 같은 격자의 정답은 1입니다.
자주 묻는 질문3
행렬에서 가장 긴 증가 경로의 시간 복잡도는 얼마인가요?
메모이제이션된 깊이 우선 탐색 또는 제거 방식을 사용하면 시간과 공간 복잡도는 O(m × n)입니다. 각 셀은 한 번만 처리하며 4개의 이웃을 살펴봅니다. 모든 셀에서 가능한 모든 경로를 시도하면 지수 시간이 걸립니다.
행렬에서 최장 증가 경로 찾기는 동적 프로그래밍 문제인가요, 아니면 그래프 문제인가요?
둘 다입니다. 방향 비순환 그래프에서 가장 긴 경로를 구하는 것으로, 위상 순서에 대한 동적 프로그래밍입니다. 셀을 값이 큰 순서에서 작은 순서로 정렬하면 또 다른 유효한 순서를 얻을 수 있으며, 정렬에 O(m × n × log(m × n))의 비용이 듭니다.
이것은 최장 증가 부분 수열과 어떻게 다른가요?
부분 수열은 원소를 건너뛸 수 있지만 순서는 유지합니다. 여기서 경로는 네 방향 중 어느 쪽이든 인접한 셀로 이동해야 합니다. 두 경우 모두 엄격히 증가하는 연쇄는 자기 자신으로 되돌아올 수 없습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def longestIncreasingPath(matrix):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
예상 출력
7