[BOJ] 1937번: 욕심쟁이 판다

https://www.acmicpc.net/problem/1937

1. 대나무의 위치를 길이 순으로 sorting합니다. O(N^2 lgN)

2. 길이가 긴 곳 부터 시작해서 자신의 상하좌우를 살펴보며 height[x][y] < height[x_new][y_new]에 대해 D[x][y] = max(D[x][y], D[x_new][y_new]+1)로 갱신합니다. 이렇게 되면 BFS 혹은 DFS로 순회를 계속하지 않고 자신의 사방만 살펴보면 되기 때문에 각 나무에 대해 상수시간이 소모됩니다. O(N^2)

D 테이블에서 최댓값을 반환합니다.

DFS / BFS를 써야할 것 같이 생겼지만 길이가 긴 곳부터 탐색하면 traversal 없이 답을 얻을 수 있습니다.

https://github.com/encrypted-def/BOJ/blob/master/1937.cpp