Longest Increasing Path in a Matrix
matrix는 m개의 행과 n개의 열로 이루어진 정수 격자이며, 행들의 목록으로 주어집니다. 경로는 한 번에 한 칸씩 위, 아래, 왼쪽 또는 오른쪽으로 이동하며(대각선 이동이나 가장자리를 넘어 이어지는 이동은 불가), 이동할 때마다 반드시 엄격하게 더 큰 값의 칸으로 이동해야 합니다. 이러한 경로 중 가장 긴 경로에 포함된 칸의 수를 반환하세요. 칸 하나만으로도 길이가 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에서 시작하는 최선의 경로는 1, 2, 7, 8, 9와 1, 6, 7, 8, 9이며, 각각 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입니다.
제출 시 숨은 테스트 +18개
후속 질문
가장 긴 경로의 길이뿐만 아니라 경로에 포함된 셀들도 반환할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
경로가 이미 방문한 셀로 다시 돌아올 수 있을까요? 이동하는 동안 값이 어떻게 변하는지 살펴보세요.
값은 증가하기만 하므로 경로에서 셀이 반복되지 않으며, 한 셀에서 시작하는 가장 긴 경로는 그 셀에 어떻게 도달했는지와 무관합니다. 이 경로의 길이는 더 큰 이웃 중 가장 좋은 이웃에서 시작하는 가장 긴 경로의 길이에 1을 더한 값입니다.
각 셀마다 그 수를 한 번 계산해 저장하세요. 직접 만든 스택을 사용해 더 큰 이웃을 대상으로 깊이 우선 탐색을 수행하여 값을 채우거나, 격자를 최고점부터 한 번에 한 층씩 벗겨 내며 층의 수를 세세요.
풀이
각 셀에서 더 큰 값을 가진 모든 이웃 셀로 화살표를 그리세요. 모든 화살표를 따라가면 값이 증가하므로, 어떤 화살표 체인도 시작점으로 되돌아올 수 없습니다. 격자는 방향 비순환 그래프이며, 과제는 그 최장 경로를 찾는 것입니다. 일반 그래프에서는 입력 크기가 크면 이 문제를 풀기 어렵지만, 사이클이 없으면 한 셀에서 시작하는 최장 경로는 그 셀에만 달려 있으므로 셀마다 한 번씩 계산하면 전체 문제의 시간 복잡도는 O(m × n)으로 줄어듭니다. 메모이제이션을 적용한 깊이 우선 탐색은 위에서 아래로 계산하고, 봉우리부터 격자를 제거하는 역방향 Kahn 알고리즘은 아래에서 위로 계산합니다.
모든 증가 경로를 따르세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
모든 셀에서 걷기를 시작합니다. 현재 셀에서 값이 더 큰 네 이웃을 각각 시도하고, 더 큰 이웃이 없을 때까지 같은 방식으로 계속 진행합니다. 각 걷기의 셀 수를 세고 가장 큰 수를 기록합니다.
걷기에는 방문 집합이 필요하지 않습니다. 매 단계마다 값이 커지므로 걷기는 어떤 셀로도 돌아올 수 없습니다. 다시 그 셀에 있으려면 그 셀의 값까지 내려와야 하기 때문입니다. 걷기는 (셀, 길이) 항목으로 이루어진 스택에 보관합니다. 항목을 꺼내면 해당 셀에서 걷기가 끝나고, 더 큰 이웃을 넣으면 걷기가 이어집니다.
이 방법은 정확하지만, 걷기가 분기되기 때문에 터무니없이 느립니다. 값이 행과 열의 합인 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들에 대해 best[cell] = 1 + max(best[nb])이며, 더 큰 이웃이 없으면 1이다. 비순환 구조이므로 이를 안전하게 재사용할 수 있다. 어떤 경로에서든 cell보다 앞에 있는 셀은 모두 더 작으므로 그 뒤에 다시 나타날 수 없고, cell에서 이어지는 최선의 경로는 그곳에 어떻게 도달했는지와 관계없이 같다. 각 best를 한 번만 계산해 저장하면, 지수적으로 늘어나는 경로 탐색 트리가 셀당 한 번 방문하는 것으로 줄어든다.
첫 번째 예시에서 9에는 더 큰 이웃이 없으므로 그곳의 best는 1이다. 그러면 8은 2, 7은 3, 6과 2는 4, 5와 1은 5, 4는 6, 3은 7이 되며, 이것이 정답이다. 각 셀은 이웃 4개를 확인하므로 작업량은 O(m × n)이다.
자연스러운 코드는 재귀적이다. 셀의 best를 반환하고, 각 더 큰 이웃에서 자기 자신을 호출하는 함수다. 호출 깊이는 따라가는 경로의 길이와 같으며, 제약 조건상 모든 셀을 지나는 경로가 가능하다. 100 × 100 격자에서 값이 앞뒤로 구불구불하게 이어지면 셀 10,000개로 이루어진 경로 하나가 만들어지지만, Python은 기본적으로 중첩 호출 1,000회에서 멈춘다. 아래 코드는 재귀 자체를 실행하므로 경로가 아무리 길어도 처리할 수 있다. 셀을 스택에 저장하고, 셀마다 네 방향 중 몇 방향을 시도했는지도 기록한다. 맨 위 셀을 살펴본다. 아직 시도하지 않은 방향이 있으면 그 방향을 시도하고, 그곳의 이웃이 더 크고 아직 처리가 끝나지 않았다면 스택에 넣는다. 네 방향을 모두 시도하면 모든 더 큰 이웃의 처리가 끝난 것이므로 셀을 스택에서 꺼내고 best를 설정한다. 이는 재귀 호출이 따랐을 순서와 정확히 같다.
이 탐색에는 순환 감지와 달리 "진행 중" 표시가 필요 없다. 스택에 있는 각 셀은 그 아래 셀보다 크므로, 맨 위 셀의 더 큰 이웃이 스택 아래쪽에 이미 있을 수 없다.
알고리즘
- 각 셀의
best를 0(아직 알 수 없음)으로 설정하고 방향 카운터를 0으로 설정합니다. best가 0인 각 셀을 스택에 넣습니다.- 맨 위 셀을 확인합니다. 아직 시도하지 않은 방향이 있으면 카운터를 증가시키고, 해당 방향의 이웃 셀이 그리드 안에 있고 더 크며 아직 처리가 끝나지 않았다면 스택에 넣습니다.
- 네 방향을 모두 시도했다면 셀을 꺼내고,
best를 더 큰 이웃들의best중 가장 큰 값에 1을 더한 값으로 설정합니다. 더 큰 이웃이 없으면 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번째 레이어입니다. 이제 일부 칸은 자신보다 큰 마지막 이웃을 잃었으므로, 남은 칸들 가운데 봉우리가 됩니다. 이들을 2번째 레이어로 제거하고, 격자가 빌 때까지 계속합니다. 레이어의 수가 정답입니다.
이유는 다음과 같습니다. 어떤 칸이 레이어 k에 속하는 것은 그 칸에서 시작하는 최장 경로의 칸 수가 정확히 k일 때입니다. 어떤 칸은 자신보다 큰 마지막 이웃이 제거된 다음 라운드에 제거되므로, 그 레이어는 자신보다 큰 이웃들의 레이어 중 가장 높은 레이어에 1을 더한 값입니다. 이는 이전 접근법의 공식 best[cell] = 1 + max(best[nb])과 같습니다. 가장 깊은 레이어는 최장 경로의 시작점에 해당합니다.
첫 번째 예제에서는 유일한 봉우리가 9입니다(이웃은 8과 2입니다). 9를 제거하면 8이 제거 가능해지고, 8을 제거하면 7이 제거 가능해집니다. 7을 제거하면 2와 6이 제거 가능해지고, 이 둘을 제거하면 1과 5가 제거 가능해집니다. 5를 제거하면 4가 제거 가능해지고, 4를 제거하면 3이 제거 가능해집니다. 총 7개 레이어이며, 경로 3, 4, 5, 6, 7, 8, 9는 각 레이어의 칸 하나씩을 거쳐 올라갑니다.
다음 레이어를 빠르게 찾으려면 각 칸에 대해 아직 남아 있는, 그 칸보다 큰 이웃의 수를 세세요. 칸 하나를 제거하면 그보다 값이 작은 각 이웃의 개수를 줄이고, 개수가 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
함정과 경계 사례
여기서 발생하는 버그는 "strictly"라는 단어, 깊은 재귀, 그리고 다른 격자 문제에서 가져온 습관 때문에 생깁니다.
>대신>=로 비교하기. 서로 이웃한 4 두 개가 있으면 각각이 다른 쪽보다 한 단계 높다고 계산되어 화살표가 순환을 만들고, 무차별 대입 탐색은 앞뒤로 영원히 오가며, 메모이제이션된 탐색은 아직 계산 중인 길이를 읽습니다.- 아주 긴 경로에서 재귀 사용하기. 재귀 탐색은 경로의 길이만큼 깊이 호출되며, 제약 조건상 모든 칸을 지나는 경로가 가능합니다. 100 × 100 격자에서 값이 지그재그로 오가면 한 경로가 10,000칸에 이르는데, 이는 Python의 기본 제한인 중첩 호출 1,000회의 10배입니다. 이렇게 긴 경로에는 직접 스택을 사용하는 반복 탐색이나 더 높은 재귀 제한(
sys.setrecursionlimitin Python)이 필요하며, 제한을 아주 높게 설정해도 인터프리터 자체의 스택이 넘칠 수 있습니다. - 플러드 필처럼 이미 방문한 칸을 건너뛰기. 처리가 끝난 칸에 도달하는 것은 막다른 길이 아닙니다. 저장된 길이가 현재 칸에 필요한 바로 그 값입니다. 그 값을 읽고 건너뛰지 마세요.
- 가장 작은 값에서만 시작하기. 첫 번째 예시에서 1로 시작하면 칸 5개를 얻지만, 정답인 7은 3에서 시작합니다. 가장 긴 경로는 더 작은 이웃이 없는 어떤 칸에서든 시작할 수 있으며, 그런 칸은 여러 개일 수 있습니다.
- 0을 반환하기. 모든 칸은 길이가 1인 경로이므로, 값이 모두 같거나 크기가 1 × 1인 격자의 정답은 1입니다. 모든 칸의 길이는 0이 아니라 1로 시작하세요.
- 제거 방식에서 값이 같은 이웃의 개수를 줄이기. 더 큰 이웃을 잃은 것은 엄밀히 더 작은 이웃뿐입니다.
자주 묻는 질문4
행렬에서 가장 긴 증가 경로의 시간 복잡도는 무엇인가요?
메모이제이션된 깊이 우선 탐색이나 위상적 제거를 사용하면 시간 복잡도는 O(m × n), 공간 복잡도는 O(m × n)입니다. m × n개의 각 셀은 한 번씩 처리되고 4개의 이웃을 상수 횟수만큼 살펴보며, 각 방법은 셀마다 숫자 하나를 저장합니다. 대신 모든 셀에서 시작하는 모든 경로를 시도하면 지수 시간이 걸립니다. 각 값이 행 번호와 열 번호의 합인 100 × 100 격자에서는 왼쪽 위 모서리에서 시작하는 경로가 10^58개를 넘습니다.
이 문제에는 왜 방문 집합이 필요하지 않을까요?
오르기만 하는 경로는 한 셀로 다시 돌아올 수 없습니다. 그 셀의 값까지 다시 내려와야 하기 때문입니다. 따라서 엄격한 증가 규칙은 이미 방문했던 셀을 다시 방문하는 것을 금지하며, 이동 그래프에는 사이클이 없습니다. 또한 메모이제이션을 안전하게 사용할 수 있는 이유도 여기에 있습니다. 특정 셀 이전의 셀들은 그 이후의 경로에 영향을 줄 수 없습니다.
행렬에서 가장 긴 증가 경로는 동적 프로그래밍 문제인가요, 그래프 문제인가요?
둘 다입니다. 이는 방향 비순환 그래프에서 가장 긴 경로를 찾는 문제이며, 위상 순서를 따라 수행하는 동적 프로그래밍입니다. 한 셀의 답은 더 큰 이웃들 중 가장 좋은 답에 1을 더한 값입니다. 메모이제이션을 사용한 깊이 우선 탐색은 탐색이 셀을 완료하는 순서대로 표를 채우고, 위상 제거는 봉우리에서 시작해 계층별로 표를 채웁니다. 셀을 값이 큰 순서부터 정렬하면 세 번째 유효한 순서를 얻을 수 있으며, 정렬에 O(m × n × log(m × n))의 비용이 듭니다.
이것은 최장 증가 부분 수열과 어떻게 다른가요?
부분 수열은 원소를 건너뛸 수 있지만 순서는 유지해야 합니다. 반면 여기서 경로는 네 방향 중 어느 방향으로든 인접한 셀로 이동해야 합니다. 부분 수열 문제는 선 위의 동적 프로그래밍 문제이고, 이 문제는 그래프 형태로 바꾼 격자 위의 동적 프로그래밍 문제입니다. 두 문제는 모두 같은 사실에 기반합니다. 엄격하게 증가하는 연결은 결코 되돌아가 순환할 수 없습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def longestIncreasingPath(matrix):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
기대값
7