• 출처 : https://www.acmicpc.net/problem/1937

• 알고리즘 : DP

• 풀이1 (top-down)

  1. 이미 방문하지 않은 모든 좌표를 순회하면서
  2. 상하좌우의 최대 거리(재귀)+1 vs 현재 좌표의 최대 거리
  3. 큰 값을 현재 좌표의 최대 거리에 저장

• 풀이2 (bottom-up)

  1. 좌표를 value값 내림차순으로 정렬 (거리 1부터 순회하기 위해)
  2. 정렬된 좌표를 순회하면서 상하좌우 비교
  3. 큰 값 + 1로 업데이트

• 소감

  • 처음엔 모든 좌표에 대해서 DFS 했는데 시간 초과 ㅜ
  • 어려워서 구글링했음
  • 검색해서 나온 DP top-down 풀이를 참조했는데 다른 분이 공유해주신 bottom-up 방식 풀이로도 코드를 짜봤다
  • 더 빠를거라고 생각했는데 더 느렸다
  • bottom-up 방식은 기본적으로 정렬이 필요해서 그런 것 같기도 하고
  • 사용되지 않는 좌표도 계산하기 때문일 수도 있을 것 같다.

코드1

# bottom-up

def init():

    board = []
    n = int(input(''))
    for i in range(n):
        line = list(map(int, input('').split(' ')))
        board.append(line)

    return n, board


def out(i, j):
    if 0 <= i < n and 0 <= j < n:
        return False
    return True


def print_line(line_list):
    for line in line_list:
        print(line)


n, board = init()

pos_list = []
for i in range(n):
    for j in range(n):
        pos_list.append((i,j,board[i][j]))
pos_list.sort(reverse=True, key=lambda x:x[2])

dist = [[1] * n for i in range(n)]

dx = [0,0,1,-1]
dy = [-1,1,0,0]

for i in range(n*n):

    curr_i, curr_j, curr_v = pos_list[i]

    max_dist = 0
    for d in range(4):

        new_i = curr_i + dy[d]
        new_j = curr_j + dx[d]

        if out(new_i, new_j):
            continue

        new_v = board[new_i][new_j]
        if curr_v < new_v:
            max_dist = max(max_dist, dist[new_i][new_j])

    if max_dist > 0:
        dist[curr_i][curr_j] = max_dist + 1

print(max([max(dist[i]) for i in range(n)]))

코드2

# top-down

import sys
sys.setrecursionlimit(99999)

def out(i, j):
    if 0 <= i < n and 0 <= j < n:
        return False
    return True


def get_distance(curr_i, curr_j):

    if dist[curr_i][curr_j] == 1:
        
        dy = [1,-1,0,0]
        dx = [0,0,1,-1]
        for i in range(4):

            new_i = curr_i + dy[i]
            new_j = curr_j + dx[i]
            if out(new_i, new_j):
                continue
            if board[curr_i][curr_j] >= board[new_i][new_j]:
                continue
            dist[curr_i][curr_j] = max(dist[curr_i][curr_j], get_distance(new_i, new_j) + 1)

        return dist[curr_i][curr_j]

    else:
        return dist[curr_i][curr_j]


def init():

    board = []
    n = int(input(''))
    for i in range(n):
        line = list(map(int, input('').split(' ')))
        board.append(line)

    return n, board


def print_line(line_list):
    for line in line_list:
        print(line)


n, board = init()

dist = [[1] * n for i in range(n)]

max_distance = 0

for i in range(n):
    for j in range(n):
        
        distance = get_distance(i, j)
        max_distance = max(max_distance, distance)
        
print(max_distance)