손가락놀이터

문제후기

1. 처음 문제를 보고 BFS를 활용해서 문제를 풀려고 했습니다. 최악의 경우 500 * 500을 BFS로 탐색하는 경우이지만 시간제한이 2초로 애매하지만 통과할 수 있다고 생각하고 코드를 작성했습니다.
2. BFS로 제출한 결과 시간초과에서 걸려서 알고리즘이 틀린 것으로 생각하고 알고리즘을 변경했습니다.
3. 다시 생각해낸 알고리즘은 DP로 최대 Heap과 연관시켜 생각했습니다. 대나무가 많은 순서로 Heap 정렬을 해준 이후 pop을 하면서 메모이제이션을 했습니다. 상하좌우의 메모 중 가장 큰 값 + 1로 메모를 갱신했습니다.
4. Heap에 남은 값이 없으면 모든 메모가 끝났으므로 메모 중에서 가장 큰 값을 출력했습니다.

문제링크

from sys import stdin
import heapq
from itertools import chain

# 상하좌우
dy = [-1,0,1,0]
dx = [0,-1,0,1]

# n 개 매트릭스
n = int(stdin.readline())
# 매트릭스 값 입력
matrix = [list(map(int, stdin.readline().split())) for _ in range(n)]
# 메모이제이션
memoization = [[0] * n for _ in range(n)]
# 최대 힙정렬 할 배열
heap = []

# 최대 힙 정렬
for y in range(n):
    for x in range(n):
        # heapq는 최소힙정렬이므로 -1을 곱해서 최대힙정렬로 한다.
        heapq.heappush(heap, (-1 * matrix[y][x], y, x))


# heap에 값이 없을때까지
while heap:
    _, y, x = heapq.heappop(heap)
    chk_arr = []
    # 상하좌우 체크
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < n and 0 <= nx < n:
            # 만약 상,하,좌,우 값이 더 크다면 해당 메모값 배열에 추가
            if matrix[y][x] < matrix[ny][nx]:
                chk_arr.append(memoization[ny][nx])

    if chk_arr: # 만약 배열에 값이 있으면 가장 큰 값 + 1
        memoization[y][x] = max(chk_arr) + 1
    else: # 배열에 값이 없으면 1
        memoization[y][x] = 1
# 메모 중에서 가장 큰 값 출력
print(max(chain(*memoization)))