⭐⭐⭐⭐[코드트리] 정수 사각형 최장 증가 수열

문제 

n×n 크기의 격자 정보가 주어졌을 때, 시작점을 적절하게 잡아 상하좌우로 인접한 칸으로 계속 칸에 적혀있는 정수값이 커지도록 이동한다고 했을 때 밟고 지나갈 수 있는 최대 칸의 수를 구하는 프로그램을 작성해보세요.

 

입력 형식 

 

첫 번째 줄에는 n이 주어집니다.
두 번째 줄부터 n개의 줄에 걸쳐 각 행에 해당하는 n개의 정수 값이 공백을 사이에 두고 주어집니다.

• 1 ≤ n ≤ 500
• 1 ≤ 주어지는 숫자 ≤ $10^9$

 

출력 형식 

가능한 경로의 숫자들 중 최솟값의 최댓값을 출력합니다.

 

입출력 예제 

예제1 

입력:

3
2 2 1
3 1 2
4 1 2

출력:

3

 

예제2

입력:

3
5 1 3
6 1 4
7 2 3

출력:

4

 

예제 설명 

 

---

백트래킹으로 풀거나 DP로 풀면 된다.

 

백트래킹 방법

 

import sys

sys.stdin=open('input.txt', 'r')

def in_range(x, y):
    return 0 <= x and x < n and 0 <= y and y < n

# 정수값이 작은 칸부터 순서대로 보며
# 4방향에 대해 최적의 칸 수를 계산합니다.
dxs = [-1, 1,  0, 0]
dys = [ 0, 0, -1, 1]

# (x, y)에서 출발하여 조건을 만족하며
# 도달할 수 있는 칸의 수 중
# 최대 칸의 수를 구합니다.
def DFS(x, y):
    # 이미 계산해본적이 있다면
    # 그 값을 바로 반환합니다.
    if dp[x][y] != -1:
        return dp[x][y]

    # 기본값은 자기자신이 됩니다.
    best = 1         # 현재 (x,y) 위치를 1번 세고 시작 

    for dx, dy in zip(dxs, dys):
        nx = x + dx
        ny = y + dy
        if in_range(nx, ny) and board[nx][ny] > board[x][y]:
            best = max(best, DFS(nx, ny) + 1)   # 다음칸으로 이동하므로 +1

    dp[x][y] = best
    return dp[x][y]

if __name__=="__main__":

    n = int(input())
    board = [list(map(int, input().split())) for _ in range(n)]
    dp = [[-1] * n for _ in range(n)]

    # 각 칸에 시작했을 떄
    # 최대로 이동할 수 있는 칸의 수 중 
    # 최댓값을 갱신합니다.
    ans = 0
    for i in range(n):
        for j in range(n):
            ans = max(ans, DFS(i, j))

    print(ans)

 

 

DP 방법 

import sys
sys.stdin=open('input.txt', 'r')

dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]

def in_range(nx, ny):
    return 0<=nx<n and 0<=ny<n

if __name__=="__main__":

    n = int(input())
    board = [list(map(int, input().split())) for _ in range(n)]
    dp = [[0] * n for _ in range(n)]

    cells = []
    ans = 0

   
    # 각 칸에 적혀있는 정수값 기준으로
    # 오름차순이 되도록 칸의 위치들을 정렬합니다.
    # 편하게 정렬하기 위해
    # (칸에 적혀있는 값, 행 위치, 열 위치) 순으로 넣어줍니다.
    for i in range(n):
        for j in range(n):
            cells.append((board[i][j], i, j))

    # 오름차순으로 정렬을 진행합니다.
    cells.sort()

    # 처음 DP 값들은 전부 1로 초기화해줍니다. (해당 칸에서 시작하는 경우)
    for i in range(n):
        for j in range(n):
            dp[i][j] = 1

    # 정수값이 작은 칸부터 순서대로 보며
    # 4방향에 대해 dp 값을 갱신해줍니다.
    for _, x, y in cells:

        # 인접한 4개의 칸에 대해 갱신을 진행합니다.
        for dx, dy in zip(dxs, dys):
            nx = x + dx
            ny = y + dy
            if in_range(nx, ny) and board[nx][ny] > board[x][y]:
                dp[nx][ny] = max(dp[nx][ny], dp[x][y] + 1)

    # 전체 수들 중 최댓값을 찾습니다.
    for i in range(n):
        for j in range(n):
            ans = max(ans, dp[i][j])

    print(ans)