어떠한 수열이 주어졌을때 이 수열의 최장 증가 부분열을 찾는것은 다이나믹 프로그래밍으로 해결할 수 있는 유명한 문제입니다.

참고자료 http://dyngina.tistory.com/16

이 문제는 2차원 배열에 대해서 최장 증가 부분열 알고리즘을 적용하면 됩니다. 모든 n*n점 (i,j)에 대해서 판다의 시작점을 정해준뒤에 dfs로 탐색하면서 얻을 수 있는 가장 긴 증가하는 수열의 길이를 얻으면 됩니다.

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <algorithm> 
using namespace std;

int forest[501][501];  
int dp[501][501]; 
int dy[4] = {1,0,-1,0}; 
int dx[4] = {0,1,0,-1};  
int n; 

bool inRange(int y,int x){
    return (y >= 0 && y < n && x >= 0 && x < n); 
}

int find(int y,int x){
    if (dp[y][x] == 0){
        dp[y][x] = 1; 
        for (int i = 0; i < 4; i++){
            int ny = y+dy[i], nx = x+dx[i];  
            if (inRange(ny,nx) && forest[ny][nx] > forest[y][x]){
                dp[y][x] = max(dp[y][x],find(ny,nx)+1); 
            }
        }
    }
    return dp[y][x];  
}

int main(){
    scanf("%d",&n);  
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            scanf("%d",&forest[i][j]);  
        }
    }
    // dp 테이블 채우기  
    int res = 0;  
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){ // 팬더의 시작좌표를 정해주고 최댓값을 갱신한다.  
            res = max(res,find(i,j));  
        }
    }
    printf("%d\n",res);  
    return 0; 
}

Ruby

def max_trail(bamboos, n=[*0...bamboos.size])
  trees = n.product(n).map {|x,y| [y,x,bamboos[x][y]] }
  nexts = ->x,y,v { trees.select {|ex,ey,ev| (ex-x).abs+(ey-y).abs <2 && ev>v} }
  trail = ->t,max=0 { t[0] ? trail[t.flat_map{|e|nexts[*e]}, max+1] : max }
  trail[trees]
end

Test

bamboos_1 = [ [0, 0],
              [0, 0] ]
expect(max_trail(bamboos_1)).to eq 1

bamboos_2 = [ [ 1, 6, 7],
              [ 2, 5, 8],
              [ 3, 4, 9] ] 
expect(max_trail(bamboos_2)).to eq 9 

bamboos_3 = [ [14, 9,12,10],
              [ 1,11, 5, 4],
              [ 7,15, 2,13],
              [ 6, 3,16, 8] ]            
expect(max_trail(bamboos_3)).to eq 4

from multiprocessing import Pool
from random import randint
import os, sys

c = os.cpu_count()
sys.setrecursionlimit(2**13)

data = list(list(int(i) for i in j.split())for j in '''14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8'''.split('\n'))


#N = 52
#data = list(list(randint(1, 100) for i in range(N)) for j in range(N))

class block(object):
    def __init__(self, N):
        self.N = N; self.l, self.r, self.u, self.d = [None]*4
    def move_lower(self):
        return list((x for x in (self.u, self.d, self.l, self.r) if x != None and x.N < self.N))
    def move_lower_chain(self, res = [], history = []):
        return (lambda temp: (res.append(history + [self.N]) if len(temp) == 0 else list(x.move_lower_chain(res, history + [x.N]) for x in temp), res)[1])(self.move_lower())

def setmap(li):
    res, n = [], len(li)
    for j in range(n):
        res.append([])
        for i in range(n):
            res[j].append(block(li[j][i]))
            if i > 0: res[j][i-1].r, res[j][i].l = res[j][i], res[j][i-1]
            if j > 0: res[j-1][i].d, res[j][i].u = res[j][i], res[j-1][i]
    temp, res = res[:], []
    return sorted((lambda temp, res: (list(list((res.append(i)) for i in j) for j in temp), res)[1])(temp, res), key = lambda x: x.N)[::-1]
def proc(m, number, cores):
    res = []
    for i in range(number, len(m), cores):
        res.append(max(map(len, m[i].move_lower_chain())))
        if max(res) > len(m)-(i+1): break
    return res
def check(m):
    with Pool() as p:
        temp = p.starmap(proc, ((m, number, c) for number in range(c)))
    return max((lambda res: (list(list(res.append(y) for y in x) for x in temp), res)[1])([]))

if __name__ == '__main__':
    m = setmap(data)
    print(check(m))

재귀함수 제한 늘려도 52가 한계네요. 52 기준 1초 미만으로 나옵니다. 파이썬 3.5.1

C 언어 입니다. 입력받은 배열 N x N 과 가장긴거리를가지는 값을 가질 배열 N x N 배열의 크기를 넘어가지 않으면서 현재의 (j, i) 보다 큰값을 찾아나가면서 1씩 증가시켜줍니다. LIS를 을 만족시키고싶었는데 재귀형식으로 된거같네요 DP도 만족시키고싶어서 최대거리를 미리 구해놨으면 그쪽방향은 배열의 값을 바로 읽게했습니다. 코드길이를 줄이면서 간단하게 하고싶은데 요령이 없네요. ㅡ.ㅜ 앞으로 더 잘하겠습니당

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>


int isPath(int **a, int i, int j)
{
    if (i == -1 || j == -1 || i == 4 || j == 4)
        return 0;

    return a[i][j];
}
int max(int a, int b, int c, int d)
{
    int max = a;
    if (max < b)
        max = b;
    if (max < c)
        max = c;
    if (max < d)
        max = d;
    return max;
}
int initial(int **a, int **l, int j, int i)
{   
    int left = 0, right = 0, up = 0, down = 0;
    if (a[j][i] < isPath(a, j , i + 1))
    {
        if (l[j][i + 1] == 0)
            right = initial(a, l, j, i + 1);
        else
            right = l[j][i + 1];
    }
    if (a[j][i] < isPath(a, j , i -1))
    {
        if (l[j][i - 1] == 0)
            left = initial(a, l, j , i -1);
        else
            left = l[j][i - 1];
    }
    if (a[j][i] < isPath(a, j + 1, i))
    {
        if (l[j + 1][i] == 0)
            down = initial(a, l, j + 1, i);
        else
            down = l[j + 1][i];
    }
    if (a[j][i] < isPath(a, j - 1, i))
    {
        if (l[j - 1][i] == 0)
            up = initial(a, l, j - 1, i);
        else
            up = l[j - 1][i];
    }

    return 1 + max(left, right, up, down);
}

int main()
{
    int n = 0;

    scanf("%d", &n);

    int **a;
    a = (int **)malloc(sizeof(int*) * n);
    for (int i = 0; i < n; i++)
        a[i] = (int*)malloc(sizeof(int) * n);

    for (int j = 0; j < n; j++)
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i][j]);


    int** LIS = (int**)malloc(sizeof(int*) * n);
    for (int i = 0; i < n; i++)
        LIS[i] = (int*)malloc(sizeof(int) * n);

    for (int j = 0; j < n; j++)
        for (int i = 0; i < n; i++)
            LIS[j][i] = 0;
    for (int j = 0; j < n; j++)
    {
        for (int i = 0; i < n; i++)
        {
            LIS[j][i] = initial(a, LIS, j, i);
        }
    }

    for (int j = 0; j < n; j++)
    {
        for (int i = 0; i < n; i++)
            printf("%d ", LIS[j][i]);
        printf("\n");
    }


}

Delphi 2010 DP(Dynamic Program방식) 사용

type
  TArrayInt2d = array of array of Integer;

function fnGeedyPanda(const M: TArrayInt2d; RCnt, CCnt: Integer; var ci, cj: Integer): Integer;
var
  V: array of array of Integer;
  CMax, i, j: Integer;

  function fnSearchValue(A, b, minVal: Integer): Integer;
  var
    val: Integer;
  begin
    if (A < 0) or (A = RCnt) or (b < 0) or (b = CCnt) then
      exit(0);

    if V[i, j] <> -1 then
     exit(V[i, j]);
    val := M[A, b];
    if val <= minVal then
      exit(0);
    result := 1 + Max(Max(fnSearchValue(A - 1, b, val), fnSearchValue(A + 1, b, val)),
      Max(fnSearchValue(A, b - 1, val), fnSearchValue(A, b + 1, val)));
  end;

begin
  SetLength(V, RCnt, CCnt);
  for i := 0 to RCnt - 1 do
    for j := 0 to CCnt - 1 do
      V[i, j] := -1; // 초기값이 -1 
  CMax := 0;
  ci := 0;
  cj := 0;
  for i := 0 to RCnt - 1 do
    for j := 0 to CCnt - 1 do
      if V[i, j] = -1 then
      begin
        V[i, j] := fnSearchValue(i, j, -1);
        if CMax < V[i, j] then
        begin
          ci := i;
          cj := j;
          CMax := V[i, j];
        end;
      end;
  result := CMax;
end;

procedure TForm4.btn욕심쟁이판다Click(Sender: TObject);
Const
  C: array [0 .. 3, 0 .. 3] of Integer = ((14, 9, 12, 10), (1, 11, 5, 4), (7, 15, 2, 13), (6, 3, 16, 8));
var
  ci, cj, CMax: Integer;
  M: TArrayInt2d;
begin
  // Dreedy 방식
  SetLength(M, 4, 4);
  for ci := 0 to 3 do
    for cj := 0 to 3 do
      M[ci, cj] := C[ci, cj];

  CMax := fnGeedyPanda(M, 4, 4, ci, cj);
  Memo1.Lines.Add(format('욕심쟁이 판다: Pos %d (%d,%d), Count: %d', [M[ci, cj], ci + 1, cj + 1, CMax]));
end;

부족한 점이 많아서 다른분보다 코드가 길은거 같아여 test

0 0

0 0

1

1 6 7

2 5 8

3 4 9

9

14 9 12 10

1 11 5 4

7 15 2 13

6 3 16 8

4

#include <stdlib.h>
#include<stdio.h>


int getMax(int t1, int t2);
int LIS(int** f, int** k, int n, int x, int y);

void main(void) {

    int n =  0;

    scanf("%d",&n);

    int** f = (int**)malloc(sizeof(int*) * n );
    for(int i = 0; i<n ; i++) {
         f[i] = (int*)malloc(sizeof(int) * n );
    }

    for(int i = 0; i<n ; i++)
        for(int j= 0; j<n ; j++) 
            scanf("%d",&f[i][j]);


    int** k = (int**)malloc(sizeof(int*) * n );
    for(int i = 0; i<n ; i++) {
         k[i] = (int*)malloc(sizeof(int) * n );
    }
    for(int i = 0; i<n ; i++)
        for(int j= 0; j<n ; j++) 
            k[i][j] = 1;
    int max = 0;
    for(int i = 0; i<n ; i++)
        for(int j= 0; j<n ; j++) 
            max = getMax(max, LIS(f, k, n, i, j));

    printf("%d\t", max);
}

int getMax(int t1, int t2) {
    if(t1 > t2)
        return t1;
    else
        return t2;
}

int LIS(int** f, int** k, int n, int x, int y) {

    for(int i = 0; i<n ; i++) {
        for(int j= 0; j<n ; j++) {
            if(f[i][j] >= f[x][y]) {
            if(i+1 < n && f[i][j] < f[i+1][j])
                k[i+1][j] = k[i][j] + 1;
            if(j+1 < n && f[i][j] < f[i][j+1])
                k[i][j+1] = k[i][j] + 1;
            if(i-1 >= 0 && f[i][j] < f[i-1][j])
                k[i-1][j] = k[i][j] + 1;
            if(j-1 >= 0 && f[i][j] < f[i][j-1])
                k[i][j-1] = k[i][j] + 1;
            }
        }
    }

    int max = 0;
    for(int i = 0; i<n ; i++) {
        for(int j= 0; j<n ; j++) {
            if(f[i][j] >= f[x][y]) {
            if(i+1 < n && f[i][j] > f[i+1][j])
                max = getMax(max ,k[i+1][j]);
            if(j+1 < n && f[i][j] > f[i][j+1])
                max = getMax(max ,k[i][j+1]);
            if(i-1 >= 0 && f[i][j] > f[i-1][j])
                max = getMax(max ,k[i-1][j]);
            if(j-1 >= 0 && f[i][j] > f[i][j-1])
                max = getMax(max ,k[i][j-1]);
            }
            k[i][j]= max + 1;
            max = 0;
        }
    }

    for(int i = 0; i<n ; i++) {
        for(int j= 0; j<n ; j++) {
            max = getMax(max ,k[i][j]);
        }
    }
    return max;
}

자바입니다

package study;

import java.util.Scanner;

public class panda {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int fr[][] = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                fr[i][j] = sc.nextInt();
            }
        }

        int temp, answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                temp = solve(n, i, j, fr);
                if (answer < temp) {
                    answer = temp;
                }
            }
        }

        System.out.println(answer);

    }

    public static int solve(int n, int x, int y, int fr[][]) {
        int result = 1;
        int dir[] = { 0, 0, 0, 0 };
        if (x > 0 && fr[x][y] < fr[x - 1][y]) {
            dir[0] = solve(n, x - 1, y, fr) + 1;
        }
        if (y > 0 && fr[x][y] < fr[x][y - 1]) {
            dir[1] = solve(n, x, y - 1, fr) + 1;
        }
        if (x + 1 < n && fr[x][y] < fr[x + 1][y]) {
            dir[2] = solve(n, x + 1, y, fr) + 1;
        }
        if (y + 1 < n && fr[x][y] < fr[x][y + 1]) {
            dir[3] = solve(n, x, y + 1, fr) + 1;
        }

        for (int i = 0; i < 4; i++) {
            if (result < dir[i]) {
                result = dir[i];
            }
        }

        return result;
    }
}

어떻게 하면 더 깔끔하게 할 수 있을거 같은데 그냥 마무리

대나무 덕후 욕심쟁이 판다 색히

#include <stdio.h>
#define SIZE 4

enum { ROOT, L, R, T, B };

int maxDepth = 0;

void next(int a[SIZE][SIZE], int row, int col, int preDir, int preVal, int preDepth) {
    int curVal = a[row][col];
    int cond = 0;
    cond = cond || row < 0;
    cond = cond || col < 0;
    cond = cond || row > SIZE - 1;
    cond = cond || col > SIZE - 1;
    cond = cond || (preDir != ROOT && preVal >= curVal);
    if(cond) {
        if(preDepth > maxDepth)
            maxDepth = preDepth;
        return; 
    }

    int curDepth = preDepth + 1;    
    if(preDir != R) next(a, row    , col - 1, L, curVal, curDepth);
    if(preDir != L) next(a, row    , col + 1, R, curVal, curDepth);
    if(preDir != B) next(a, row - 1, col    , T, curVal, curDepth);
    if(preDir != T) next(a, row + 1, col    , B, curVal, curDepth);
}

int main() {
    int a[SIZE][SIZE] = {
                    { 14,  9, 12, 10 }, 
                    {  1, 11,  5,  4 },
                    {  7, 15,  2, 13 },
                    {  6,  3, 16,  8 }
                };

    for(int row = 0; row < SIZE; row++) {
        for(int col = 0; col < SIZE; col++) {
            next(a, row, col, ROOT, a[row][col], 0);
        }
    }
    printf("maxDepth: %d", maxDepth);   
    return 0;
}

자바입니다. 간단하게 작성하려고했는데 생각보다 길게 작성이됬네요.

public class GreedyPanda {
    private int[][] forest;
    private int size;
    private int MAX;

    private final int[] X = { 0, 1, 0, -1 };
    private final int[] Y = { 1, 0, -1, 0 };

    public GreedyPanda(int size, int[][] forest) {
        this.size = size;
        this.MAX = size * size;
        this.forest = forest;
    }

    public int getMaximumAliveDay() {
        int result = 0;
        int temp = 0;
        for (int i = 0; i < this.size; i++) {
            for (int j = 0; j < this.size; j++) {
                temp = findMaximumPath(i, j);
                result = temp > result ? temp : result;
                if (result == this.MAX) {
                    return result;
                }
            }
        }
        return result;
    }

    private int findMaximumPath(int x, int y) {
        int result =1;
        int nextX, nextY, temp;

        for (int i = 0; i < 4; i++) {
            temp = 0;
            nextX = x + X[i];
            nextY = y + Y[i];

            if (inForest(nextX, nextY) && forest[x][y] < forest[nextX][nextY]) {
                if ((temp = findMaximumPath(nextX, nextY)+1) > result) {
                    result = temp;
                }
            }
        }
        return result;
    }

    private boolean inForest(int x, int y) {
        return (x >= 0 && x < size && y >= 0 && y < size);
    }
}

Ruby

def max_trail(bamboos, n=[*0...bamboos.size])
  trees = n.product(n).map {|x,y| [y,x,bamboos[x][y]] }
  nexts = ->x,y,v { trees.select {|ex,ey,ev| (x-ex).abs+(y-ey).abs <2 && ev>v } }
  trail = ->xy,cnt=1,t=nexts[*xy] { t[0]? t.map {|e| trail[e,cnt+1] } : cnt }
  trees.map(&trail).flatten.max
end


Test
bamboos_1 = [ [0, 0],
              [0, 0] ]
expect(max_trail(bamboos_1)).to eq 1

bamboos_2 = [ [ 1, 6, 7],
              [ 2, 5, 8],
              [ 3, 4, 9] ] 
expect(max_trail(bamboos_2)).to eq 9 

bamboos_3 = [ [14, 9,12,10],
              [ 1,11, 5, 4],
              [ 7,15, 2,13],
              [ 6, 3,16, 8] ]            
expect(max_trail(bamboos_3)).to eq 4

#include<iostream>
#include<vector>
using namespace std;
#define FSIZE 4
int arr[FSIZE][FSIZE] = { { 14, 9, 12, 10 },{ 1, 11, 5, 4 },{ 7, 15, 2, 13 },{ 6, 3, 16, 8 } };
int xRot[4] = { 0, 1, 0, -1 };
int yRot[4] = { 1, 0, -1, 0 };

int findPath(int _x, int _y, vector<int> v);
int main()
{
    vector<int> vvv;
    int pSuvDate = 0;
    int cSuvDate = 0;

    for (int i = 0; i < FSIZE; i++)
    {
        for (int j = 0; j < FSIZE; j++)
        {
            cout << arr[i][j] << " : ";
            vvv.push_back(arr[i][j]);
            cSuvDate = findPath(i, j, vvv);
            if (pSuvDate < cSuvDate)
                pSuvDate = cSuvDate;
            vvv.clear();
            cout << endl;

        }
    }
    cout << "result" << pSuvDate << endl;
    return 0;
}
int findPath(int _x, int _y, vector<int> v)
{
    vector<int>  vvv = v;
    int suvDate[4] = { 1, 1, 1, 1 };
    bool isEnd = true;
    for (int i = 0; i < 4; i++)
    {
        if (0 <= _y + yRot[i] && _y + yRot[i] <= FSIZE-1 && 0 <= _x + xRot[i] && _x + xRot[i] <= FSIZE-1)
        {
            if (arr[_x][_y] < arr[_x + xRot[i]][_y + yRot[i]])
            {
                vvv.push_back(arr[_x + xRot[i]][_y + yRot[i]]);
                suvDate[i] += findPath(_x + xRot[i], _y + yRot[i], vvv);
                isEnd = false;
                vvv.pop_back();
            }
        }
    }
    int a = 0;
    if (isEnd)
    {
        cout << endl;
        for (int i = 0; i < vvv.size(); i++)
            cout << "=" << vvv[i];
    }
    for (int i = 0; i < 4; i++)
    {
        if (suvDate[a] <= suvDate[i])
            a = i;
    }
    return suvDate[a];
}

시작점부터 더 큰 값이 있는 칸으로 옮겨갈 수 있는 최대 길이..

일단 main()부터..

int main(int argc, const char * argv[]) {
    int area[] = {
        14,9,12,10,
        1,11,5,4,
        7,15,2,13,
        6,3,16,8
    };
    int days = howLongWillPandaLive(area, 4);
    printf("%d\n", days);
    return 0;
}

쉽게 접근하면 각 지점에서 모두 최대로 살수있는 날을 구해서 그 중의 가장 큰값을 구하면 될듯.

int howLongWillPandaLive(int area[], int n) {
    int max = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int days = howLong(area, n, i, j);
            if (max < days) {
                max = days;
            }
        }
    }
    return max;
}

시작점으로부터 가장 오래 살 수 있는 날은.. 재귀적으로 모든 가능한 방향으로 갈 수 있는 만큼.. 마치 depth first search 같네요. 일단 재귀로 풀어봅니다.

int howLong(int area[], int n, int r, int c) {
    int days = 1;
    int current = area[r*n + c];

    // 더 많은 쪽으로 옮겨갈 수 있다.
    if (r > 0 && area[(r-1)*n + c] > current) days = max(days, 1+howLong(area, n, r-1, c));
    if (c > 0 && area[r*n + (c-1)] > current) days = max(days, 1+howLong(area, n, r, c-1));
    if (r+1 < n && area[(r+1)*n + c] > current) days = max(days, 1+howLong(area, n, r+1, c));
    if (c+1 < n && area[r*n + (c+1)] > current) days = max(days, 1+howLong(area, n, r, c+1));

    return days;
}

끝!

그런데 howLong이 너무 많이 불리는 문제가.. 그 값은 늘 같음 (그 점에서 시작해서 가장 오래 살수 있는 날) 그럼 기억해두기 (memoization)

int howLongWillPandaLive(int area[], int n) {
    int *memo = (int*)calloc(n*n, sizeof(int));

    int max = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int days = howLong(area, n, i, j, memo);
            if (max < days) {
                max = days;
            }
        }
    }
    free(memo);
    return max;
}

howLong()은 memo에 이미 값이 있으면 그 값을 바로 반환하고 아니면 계산해서 기억해두기

int howLong(int area[], int n, int r, int c, int memo[]) {
    int days = 1;
    int current = area[r*n + c];

    if (memo[r*n + c] > 0) return memo[r*n + c];

    // 더 많은 쪽으로 옮겨갈 수 있다.
    if (r > 0 && area[(r-1)*n + c] > current) days = max(days, 1+howLong(area, n, r-1, c, memo));
    if (c > 0 && area[r*n + (c-1)] > current) days = max(days, 1+howLong(area, n, r, c-1, memo));
    if (r+1 < n && area[(r+1)*n + c] > current) days = max(days, 1+howLong(area, n, r+1, c, memo));
    if (c+1 < n && area[r*n + (c+1)] > current) days = max(days, 1+howLong(area, n, r, c+1, memo));

    memo[r*n + c] = days;
    return days;
}

c++ 재귀로 풀어봤습니다.

#include<iostream>

using namespace std;

int maxDay = 0;

void find(int i, int j, int n, int input[4][4], int day)
{
    if(maxDay < day)
        maxDay = day;

    day++;

    if(i > 0 && input[i-1][j] > input[i][j]) //up
        find(i-1,j,n,input,day);

    if(i < n-1 && input[i+1][j] > input[i][j]) //down
        find(i+1,j,n,input,day);

    if(j > 0 && input[i][j-1] > input[i][j]) //left
        find(i,j-1,n,input,day);

    if( j < n-1 && input[i][j+1] > input[i][j]) //right
        find(i,j+1,n,input,day);

    return;
}

void main()
{
    cout<<"Hello Stranger!!?"<<endl;

    int input[4][4] = { 14,9,12,10, 1,11,5,4, 7,15,2,13, 6,3,16,8 };

    for(int i=0; i<4; i++)
    {
        int day = 1;

        for(int j=0; j<4; j++)
            find(i,j,4,input,day);
    }

    cout<<maxDay;

}

def greedyPanda(n,bamboo,i,j):
    max_cnt = 1 
    if bamboo.dirlst[i][j] != '0000':
        for a,b in enumerate(bamboo.dirlst[i][j]):
            cnt = 1
            if b != '1':
                continue
            if a == 0:
                cnt = greedyPanda(n,bamboo,i-1,j) + 1
            if a == 1:
                cnt = greedyPanda(n,bamboo,i,j+1) + 1
            if a == 2:
                cnt = greedyPanda(n,bamboo,i+1,j) + 1
            if a == 3:
                cnt = greedyPanda(n,bamboo,i,j-1) + 1
            if cnt > max_cnt:
                max_cnt = cnt
    return max_cnt

class Bamboo_g:
    def __init__(self,n,lst):
        self.n = n
        self.lst = [[None for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            for j in range(self.n):
                self.lst[i][j] = int(lst[i][j])
        self.dirlst = self.createDirect(lst)

    def createDirect(self,lst):
        dir_lst = [[None for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            for j in range(self.n):
                num = 0
                add_zero = ''
                if i > 0:
                    if self.lst[i-1][j] > self.lst[i][j]:
                        num += 8
                if i < n-1:
                    if self.lst[i+1][j] > self.lst[i][j]:
                        num += 2
                if j > 0:
                    if self.lst[i][j-1] > self.lst[i][j]:
                        num += 1
                if j < n-1:
                    if self.lst[i][j+1] > self.lst[i][j]:
                        num += 4
                if num < 2:
                    add_zero += '0'
                if num < 4:
                    add_zero += '0'
                if num < 8:
                    add_zero += '0'
                dir_lst[i][j] = add_zero+bin(num)[2:]
        return dir_lst

n = int(input(':'))
lst = [[None for j in range(n)] for i in range(n)]

for i in range(n):
    tmp_line = input().split(' ')
    for j in range(n):
        lst[i][j] = tmp_line[j]

b = Bamboo_g(n,lst)

max_cnt = 0
for i in range(n):
    for j in range(n):
        cnt = greedyPanda(n,b,i,j)
        max_cnt = max(max_cnt,cnt)
print(max_cnt)

n*n 크기의 방향리스트를 만들어서 리스트를 참조하며 재귀적으로 함수를 호출합니다.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Panda {

    static int n;
    static int m;
    static int[][] a;

    public static void main(String[] args) throws FileNotFoundException {
        String path = Panda.class.getResource("").getPath();
        Scanner sc = new Scanner(new File(path + "Panda.txt"));
        n = sc.nextInt();
        a = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                recursive(i, j, a[i][j], 0);
            }
        }

        System.out.println(m);
    }


    private static void recursive(int y, int x, int s, int c) {
        //좌
        System.out.print(s);
        if (x > 0 && s < a[y][x - 1]) {
            c = c + 1;
            recursive(y, x - 1, a[y][x - 1], c);
        }
        //상
        if (y > 0 && s < a[y - 1][x]) {
            c = c + 1;
            recursive(y - 1, x, a[y - 1][x], c);
        }
        //우
        if (x < n - 1 && s < a[y][x + 1]) {
            c = c + 1;
            recursive(y, x + 1, a[y][x + 1], c);
        }
        //하
        if (y < (n - 1) && s < a[y + 1][x]) {
            c = c + 1;
            recursive(y + 1, x, a[y + 1][x], c);
        }

        if (m < c) {
            m = c;
        }
    }
}

def LIS(i, j):
    global life
    if life[i][j] >= 0:
        return life[i][j]

    M = 0
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        k, l = i + dx, j + dy
        if 0 <= k < N and 0 <= l < N and bamboo[k][l] > bamboo[i][j]:
                M = max(M, LIS(k, l))

    life[i][j] = M + 1
    return life[i][j]


N = 4
bamboo = [[14, 9, 12, 10], [1, 11, 5, 4], [7, 15, 2, 13], [6, 3, 16, 8]]
life = [[-1 for y in bamboo[0]] for x in bamboo]

M = 0
for i in range(N):
    for j in range(N):
        M = max(M, LIS(i, j))

print(M)

haskell

import Data.Array
import Data.Function
import Data.Function.Memoize

solution :: Array (Int, Int) Int -> Int
solution arr = maximum $ flip fmap (indices arr) $ memoFix $
    \r x -> 1 + foldr max 0 (r <$> filter (on (<) (arr!) x) (nbrs x))
    where nbrs (a,b) = filter (inRange . bounds $ arr) [(a+1,b),(a-1,b),(a,b+1),(a,b-1)]

main = print $ solution $ listArray ((0,0), (3,3)) [14,9,12,10,1,11,5,4,7,15,2,13,6,3,16,8]

아이디어 : 항상 자기 자신보다 큰 수로 이동하기 때문에 자기 자신에 돌아오는 길은 없다. 따로 DP를 사용할 필요가 없고, max 값만 구하면 되기 때문에 n*n 개 각각의 경로의 수를 카운트해서 그 중 가장 긴 경로를 출력한다.

def panda(arr:Array[Array[Int]]):Int = {
      val direction = List((1, 0), (0, 1), (-1, 0), (0, -1))

      def countPath(x: Int, y: Int, cnt: Int):Int = {
        if(x >= 0 && y >= 0 && x < arr.length && y < arr.length){
          var maxCnt = cnt
          for((a, b) <- direction){
            if(x + a >= 0 && y + b >= 0 && x + a < arr.length && y + b < arr.length && arr(x + a)(y + b) > arr(x)(y)){
              maxCnt = Math.max(maxCnt, countPath(x + a, y + b, cnt + 1))
            }
          }
          maxCnt
        }
        else {
          cnt
        }
      }

      var max = 0
      for(i <- 0 until arr.length; j <- 0 until arr.length){
        max = Math.max(max, countPath(i, j, 1))
      }
      max
    }
    println(panda(
      Array(
        Array(14 ,9, 12 ,10),
        Array(1 ,11, 5 ,4),
        Array(7 ,15, 2 ,13),
        Array(6 ,3, 16 ,8)
      )
    ))

단순 recurison

def panda(mat,x,y):
    dr = ( (1,0),(-1,0),(0,1),(0,-1) )

    nib = []
    for dx,dy in dr:
        if 0<=x+dx<len(mat) and 0<=y+dy<len(mat[0]) and mat[x][y] < mat[x+dx][y+dy]:
            nib.append(panda(mat,x+dx,y+dy))
    if not nib: return 1
    return max(nib)+1

sample = '''\
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8'''

board = [[*map(int,i.split())] for i in sample.split('\n')]

print(max(panda(board,i,j) for i in range(len(board)) for j in range(len(board[0]))))

메모이제이션

memo = {}
def panda(mat,x,y):
    if (x,y) in memo: return memo[(x,y)]
    dr = ( (1,0),(-1,0),(0,1),(0,-1) )

    nib = []
    for dx,dy in dr:
        if 0<=x+dx<len(mat) and 0<=y+dy<len(mat[0]) and mat[x][y] < mat[x+dx][y+dy]:
            nib.append(memo[(x+dx,y+dy)] if (x+dx,y+dy) in memo else panda(mat,x+dx,y+dy))

    if not nib: memo[(x,y)] = 1
    else: memo[(x,y)] = max(nib)+1
    return memo[(x,y)]

sample = '''\
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8'''

board = [[*map(int,i.split())] for i in sample.split('\n')]

print(max(panda(board,i,j) for i in range(len(board)) for j in range(len(board[0]))))

class Panda:
    def __init__(self, size, data):
        self.n = size
        self.d = data
        self.direc = ((1,0),(-1,0),(0,1),(0,-1))

    def max_depth(self, x, y):
        c = self.d[(x,y)]
        temp = []
        for dx, dy in self.direc:
            nx = x + dx
            ny = y + dy
            if 0<=nx<self.n and 0<=ny<self.n:
                if self.d[(nx,ny)] > c:
                    temp.append(self.max_depth(nx,ny))
        if temp:
            return 1 + max(temp)
        else:
            return 1

    def find_max_life(self):
        ans = 0
        for x in range(self.n):
            for y in range(self.n):
                a = self.max_depth(x,y)
                if a > ans:
                    ans = a
        print(ans)


n = int(input())

data = {}
for y in range(n):
    line = input().split(' ')
    for x in range(n):
        data[(x,y)] = int(line[x])


P = Panda(n, data)
print('정답 :')
P.find_max_life()

4
14 9 16 10
1 11 12 4
2 15 7 13
3 5 6 8
정답 :
8

파이썬 3.7 사용. 출제의도와 맞는 풀이 방식인진 잘 모르겠지만 풀어봤습니다.

def isNum(S): #문자열S를 받아서 S가 자연수이면 True
    try:
        N=int(S)
        if N>=1:
            return True
        else:
            return False
    except:
        return False

class GreedyPanda:
    def __init__(self):
        self.K=1 #판다의 수명 초기값 (일)

    def get_N(self): #N 입력받기
        while(True): 
            tmp=input('N: ')
            N=int(tmp) if isNum(tmp) and int(tmp)<=500 else 0
            if N:
                self.N=N
                break
            else:
                print('1<=N<=500인 정수 N을 입력하세요\n')

    def get_bamboo(self): #장소별 대나무양 입력받기(중복없이 N**2개 자연수)
        N=self.N
        while(True): 
            print('장소별 대나무 양을 입력하세요')
            self.bamboo=[]
            bamboo_set=set(self.bamboo) #중복검사용
            i=1
            while(i<=N):
                tmp=input('{}행: '.format(i)).split(' ')
                bamboo_col=[int(x) for x in tmp if isNum(x)]
                if len(set(bamboo_col))==N:
                    bamboo_set.update(bamboo_col)
                    self.bamboo.append(bamboo_col)
                    i+=1
                else:
                    print('Error. 다시 입력하세요')
            if len(bamboo_set)!=N**2:
                print('중복된 값이 있습니다. 다시 입력하세요.\n')
            else:
                break
        return self.bamboo

    #본문
    def Panda_Life(self): #대나무량을 받고 판다의 수명 K를 반환
        self.K=1 #초기화
        self.get_N()
        self.get_bamboo()
        self.choice=[]
        self.dead_point=[]
        N=self.N
        for i,v1 in enumerate(self.bamboo):
            col=[]
            for j,v2 in enumerate(v1):
                r='' #'상하좌우'순서대로 이웃한 지역의 대나무양이 더 많으면 1, 적으면 0, 지정한 범위를 넘어가면 x
                     # ex> r='101x' 위 지역과 왼쪽 지역이 대나무양이 더 많고, 오른쪽에는 더이상 지역이 없다   
                #상
                if i==0: #위로 더 이상 이동할 지역이 존재하지 않음
                    r+='x'
                else: #위 지역에 대나무가 더 많으면 1 아니면 0
                    r+='1' if self.bamboo[i-1][j]>v2 else '0'
                #하
                if i==N-1: #아래로 더 이상 이동할 지역이 존재하지 않음
                    r+='x'
                else: #아래 지역에 대나무가 더 많으면 1 아니면 0
                    r+='1' if self.bamboo[i+1][j]>v2 else '0'
                #좌
                if j==0: #왼쪽으로 더 이상 이동할 지역이 존재하지 않음
                    r+='x'
                else: #왼쪽 지역에 대나무가 더 많으면 1 아니면 0
                    r+='1' if self.bamboo[i][j-1]>v2 else '0'
                #우
                if j==N-1: #오른쪽으로 더 이상 이동할 지역이 존재하지 않음
                    r+='x'
                else: #오른쪽 지역에 대나무가 더 많으면 1 아니면 0
                    r+='1' if self.bamboo[i][j+1]>v2 else '0'
                col.append(r)
                if '1' not in r: # 판다가 이동할 선택지가 없는 포인트. 판다는 이 포인트들에서만 죽는다.
                    self.dead_point.append([i,j]) #좌표를 저장
            self.choice.append(col)

        #판다가 죽게 될 위치에서부터 역추적하여 최장루트의 길이를 찾는다
        for p in self.dead_point:  
            self.cycle(p[0], p[1], 1) #재귀함수 호출

        print('판다의 최대수명은 {}일 입니다.'.format(self.K)) #최종 출력

    def cycle(self, i,j, days): #재귀함수. (i, j)에서 역순으로 거슬러올라간다(=0인 방향으로 추적)
        if self.choice[i][j][0]=='0': #상
            self.cycle(i-1,j,days+1)
        if self.choice[i][j][1]=='0': #하
            self.cycle(i+1,j,days+1)
        if self.choice[i][j][2]=='0': #좌
            self.cycle(i,j-1,days+1)
        if self.choice[i][j][3]=='0': #우
            self.cycle(i,j+1,days+1)
        elif days>self.K: #더 이상 갈곳이 없음(=출발점으로 돌아옴) and 최대길이(수명) 갱신
            self.K=days
            #루프 종료

if __name__=="__main__":
    a=GreedyPanda()
    a.Panda_Life()

inp="""14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8"""
inp2="""1 6 7
2 5 8
3 4 9"""
inp3="""0 0
0 0"""
lst=[ln.split(" ") for ln in inp.split("\n")]
lst2=[ln.split(" ") for ln in inp2.split("\n")]
lst3=[ln.split(" ") for ln in inp3.split("\n")]

elst=[]
sd=1
def solve(y,x,lst):
    global sd
    cn=int(lst[y][x])
    for dy,dx in [(1,0),(0,1),(-1,0),(0,-1)]:
        ny,nx=y+dy,x+dx
        if 0<=ny<len(lst) and 0<=nx<len(lst[0]):
            if int(lst[ny][nx])>cn:
                sd+=1
                solve(ny,nx,lst)
                sd-=1
    elst.append(sd)
    return elst

출력

elst=[] #elst는 매번 빈 리스트로 초기화
for y in range(len(lst)):
    for x in range(len(lst[0])):
        solve(y,x,lst)
print(max(elst)) #4

elst=[]
for y in range(len(lst2)):
    for x in range(len(lst2[0])):
        solve(y,x,lst2)
print(max(elst)) #9

elst=[]
for y in range(len(lst3)):
    for x in range(len(lst3[0])):
        solve(y,x,lst3)
print(max(elst)) #1