뱀 시퀀스(Snake Sequence)란?
숫자로 채워진 2차원 격자(grid)에서 뱀 시퀀스를 찾는 문제를 생각해 보겠습니다. 가능한 시퀀스가 여러 개라면 그중 하나만 반환하면 됩니다.
뱀 시퀀스는 격자에서 서로 인접한 칸의 숫자들을 연결해 만든 수열입니다. 조건은 간단합니다. 현재 값이 셀 (a, b)에 있을 때, 오른쪽 칸 (a, b+1) 또는 아래쪽 칸 (a+1, b)에 있는 값이 현재 값과 정확히 ±1만큼 차이가 나야 합니다. 즉, 값이 1씩 오르거나 내려가는 방향으로만 이동할 수 있습니다.
예제로 살펴보기
다음과 같은 4×4 격자가 주어졌다고 가정해 보겠습니다.
| 10 | 7 | 6 | 3 |
| 9 | 8 | 7 | 6 |
| 8 | 4 | 2 | 7 |
| 2 | 2 | 2 | 8 |
이 격자에서 찾을 수 있는 최장 뱀 시퀀스의 길이는 6이며, 실제 경로는 다음과 같습니다.
- 10 (0, 0)
- 9 (1, 0)
- 8 (1, 1)
- 7 (1, 2)
- 6 (1, 3)
- 7 (2, 3)
- 8 (3, 3)
매 단계마다 값이 1씩 변하면서 아래 또는 오른쪽으로만 이동하는 것을 확인할 수 있습니다.
풀이 접근 방식: 동적 계획법(DP)
가능한 모든 경로를 일일이 탐색하는 것은 매우 비효율적입니다. 대신 동적 계획법을 활용해 각 칸에서 끝나는 뱀 시퀀스의 최대 길이를 저장하는 룩업(lookup) 테이블을 만들면 O(M×N) 시간 안에 문제를 해결할 수 있습니다.
핵심 아이디어
lookup[i][j]는 셀 (i, j)에서 끝나는 뱀 시퀀스의 최대 길이를 의미합니다.- 위쪽 칸 (i-1, j) 또는 왼쪽 칸 (i, j-1)의 값과 현재 값의 차이가 ±1이라면, 해당 칸의 최장 길이에 1을 더한 값을 후보로 삼습니다.
- 모든 칸을 순회한 뒤 룩업 테이블에서 가장 큰 값을 찾으면 전체 최장 길이와 그 끝점 좌표를 알 수 있습니다.
- 마지막으로 끝점에서 출발해 룩업 값이 하나씩 줄어드는 방향으로 거슬러 올라가면 실제 경로를 복원할 수 있습니다.
경로 복원 함수 get_path()
get_path() 함수는 룩업 테이블과 최장 시퀀스의 끝 좌표 (i, j)를 받아 경로를 역추적합니다. 현재 칸의 룩업 값보다 1 작은 값이 위쪽 또는 왼쪽 칸에 있는지 확인해 한 칸씩 이동하고, 룩업 값이 0인 시작 지점에 도달하면 종료합니다.
메인 로직 흐름
- M×N 크기의 룩업 테이블을 0으로 초기화합니다.
- 최대 길이(length_max)와 끝점 좌표(max_row, max_col)를 0으로 설정합니다.
- 모든 칸을 순회하며 위쪽·왼쪽 이웃과의 값 차이가 1인지 검사하고, 조건을 만족하면 룩업 값을 갱신합니다.
- 갱신된 값이 현재 최대치보다 크면 최대 길이와 끝점 좌표를 함께 기록합니다.
- 순회가 끝나면 최대 길이를 출력하고, get_path()로 경로를 복원한 뒤 역순으로 출력합니다.
파이썬 구현 코드
M = 4
N = 4
# 최장 시퀀스의 끝점에서 시작 지점까지 경로를 역추적하는 함수
def get_path(lookup, grid, i, j):
path = list()
pt = [i, j]
path.append(pt)
while (lookup[i][j] != 0):
# 위쪽 칸에서 이어진 경우
if (i > 0 and lookup[i][j]-1 == lookup[i-1][j]):
pt = [i-1, j]
path.append(pt)
i -= 1
# 왼쪽 칸에서 이어진 경우
elif (j > 0 and lookup[i][j]-1 == lookup[i][j-1]):
pt = [i, j-1]
path.append(pt)
j -= 1
return path
def get_sequence(grid):
# 각 칸에서 끝나는 최장 뱀 시퀀스의 길이를 저장하는 DP 테이블
lookup = [[0 for i in range(N)] for j in range(M)]
length_max = 0
max_row = 0
max_col = 0
for i in range(M):
for j in range(N):
if (i or j):
# 위쪽 칸과 값 차이가 1인 경우
if (i > 0 and abs(grid[i-1][j] - grid[i][j]) == 1):
lookup[i][j] = max(lookup[i][j], lookup[i-1][j] + 1)
if (length_max < lookup[i][j]):
length_max = lookup[i][j]
max_row = i
max_col = j
# 왼쪽 칸과 값 차이가 1인 경우
if (j > 0 and abs(grid[i][j-1] - grid[i][j]) == 1):
lookup[i][j] = max(lookup[i][j], lookup[i][j-1] + 1)
if (length_max < lookup[i][j]):
length_max = lookup[i][j]
max_row = i
max_col = j
print("Maximum length:", length_max)
path = get_path(lookup, grid, max_row, max_col)
print("Sequence is:")
for ele in reversed(path):
print(grid[ele[0]][ele[1]], " [", ele[0], ", ", ele[1], "]", sep="")
grid = [
[10, 7, 6, 3],
[9, 8, 7, 6],
[8, 4, 2, 7],
[2, 2, 2, 8]]
get_sequence(grid)입력
[[10, 7, 6, 3], [9, 8, 7, 6], [8, 4, 2, 7], [2, 2, 2, 8]]
출력
Maximum length: 6 Sequence is: 10 [0, 0] 9 [1, 0] 8 [1, 1] 7 [1, 2] 6 [1, 3] 7 [2, 3] 8 [3, 3]
정리
이 문제는 동적 계획법을 적용하기 좋은 전형적인 격자 탐색 문제입니다. 각 칸을 한 번씩만 처리하므로 시간 복잡도는 O(M×N)이며, 룩업 테이블 저장에 O(M×N)의 공간이 필요합니다. 경로 복원까지 포함해도 추가 비용은 선형 수준에 그치므로, 큰 격자에서도 효율적으로 동작합니다.