[DFS/DP] 최대의 케이스를 구할 때, 경로별 탐색 후 대표 예제

상, 하, 좌, 우 등의 방문을 수행했을 때, 모든 반복을 마친 최종 경우의 수가 각각 cnt1, cnt2, cnt3, cnt4라고 할 때

 

이 때 최대의 경우의 수를 구하는 문제 유형들이 있다. 

 

아래가 대표적인 유형이고 첫 번째 문제는 아래 쪽으로 내려갈 때 좌, 우 중 어느 곳이 더 최대인지

두 번째 문제의 경우 상, 하, 좌, 우 중 어느 곳이 더 최대인지 문제를 푸는 방법들이다. 

 

이 것들을 잘 익혀서 문제에 써먹어보자. 유형이 비슷하니 꼭 반복숙달하기를

 

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=python3

프로그래머스

def solution(triangle) :
    return DFS(triangle,0,0,0)

def DFS(triangle,x,y,sums1=0,sums2=0,memo={}) :
    if x == len(triangle) :
        return max(sums1,sums2)

    if (x,y) in memo :
        return memo[(x,y)]

    sums1 = DFS(triangle,x+1,y,memo=memo) + triangle[x][y]
    sums2 = DFS(triangle,x+1,y+1,memo=memo) + triangle[x][y]
        
    sums = max(sums1,sums2)
    memo[(x,y)] = sums
    return sums

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

1937번: 욕심쟁이 판다

import sys
sys.setrecursionlimit(40000) ## 이게 참 백준의 아쉬움...

N = int(input())

maps = [ [int(x) for x in input().split()] for _ in range (N)]

#### 주의, 칸의 수이기 때문에 시작은 1로
def DFS(maps,x,y,sums1=1,sums2=1,sums3=1,sums4=1) :

    if (x,y) in memo :
        return memo[(x,y)]

    ### 종료 조건은 더 이상 다음 곳을 먹을 수 없을 때!
    before_x = x-1
    before_y = y-1
    after_x = x+1
    after_y = y+1

    # 아래
    if after_x < N :
        if maps[x][y] < maps[after_x][y] : 
            sums1 = DFS(maps,after_x,y)+1
    # 위
    if before_x >= 0 :
        if maps[x][y] < maps[before_x][y] :
            sums2 = DFS(maps,before_x,y)+1
    # 오른쪽
    if after_y < N :
        if maps[x][y] < maps[x][after_y] :
            sums3=  DFS(maps,x,after_y)+1
    # 왼쪽
    if before_y >= 0 :
        if maps[x][y] < maps[x][before_y] : 
            sums4 = DFS(maps,x,before_y)+1
            
    memo[(x,y)] = max(sums1,sums2,sums3,sums4)
    return memo[(x,y)]

maxs = 0
memo = {}
for i in range(N) :
    for j in range(N) :
        if (i,j) in memo :
            results = memo[(i,j)]
        else : 
            results = DFS(maps,i,j)
            memo[(i,j)] = results
        if results > maxs :
            maxs = results
print(maxs)