[백준] 19947번 욕심쟁이 판다

사용 언어 - Python3

문제 -  19947번 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

 

정답

2차원 그래프의 DP

# 모든 점을 방문
# 방문한 뒤 이동할 수 있는 모든 경우의 수를 재귀로 구현한다
# 재귀로 구현한 뒤 DP로 바꾼다.

 

현재 위치 graph[y][x] / 상하좌우 이동 dy,dx / 이동위치 ey, ex

ey = y + dy, ex = x + ex

 

조건1) n*n 그래프 안에 있어야함 0<= ex,ey < n

조건2) 이동하는 곳의 값이 더 커야함 graph[y][x] < graph[ey][ex]

 

 

1번 재귀함수

=> 조건 만족시 recur(ey,ex) + 1

시작 위치에서 2번 이동한 경우 2+1 = 3

=> 조건 불만족시 0

마지막 위치라 더이상 갈 수 없는 경우 0

 

상하좌우 이동했을 때 가장 큰 값을 return

max(recur(y-1,x), recur(y+1,x), recur(y,x+1), recur(y,x-1)) 

def recur(y,x):
    for dy, dx in [[0,-1],[0,1],[-1,0],[1,0]]: # 상하좌우 이동
        # ey,ex로 좌표이동
        ey = y + dy
        ex = x + dx        
        if 0 <= ey < n and 0 <= ex < n : # 그래프 넘어가면 무시
            if graph[y][x] < graph[ey][ex]: # 이동 가능한 경우
                # 시작 위치에서 두 번 이동시 2
                # 마지막 위치는 더이상 갈 곳이 없어서 0
                return recur(ey,ex) + 1
        return 0 # 조건 불만족시 0
    # 상하좌우 이동했을 때 가장 큰 값
    return max(recur(y-1,x), recur(y+1,x), recur(y,x+1), recur(y,x-1))

n = int(input()) # 대나무 숲의 크기
graph = [list(int(input().split())) for_ in range(n)] # 대나무 숲의 정보
# 모든 점을 방문
for y in range(n):
    for x in range(n):
        recur(y,x)

 

2번 재귀함수 point로 저장

=> 조건 만족시

상하좌우 이동했을 때 가장 큰 값을 point로 저장

point = max(point,recur(ey,ex) + 1)

=> 조건 불만족시 0

return point

# 출발 위치가 상관없음 & 가장 많이 이동
def recur(y,x):
    point = 0
    for dy, dx in [[0,-1],[0,1],[-1,0],[1,0]]: # 상하좌우 이동
        # ey,ex로 좌표이동
        ey = y + dy
        ex = x + dx        
        if 0 <= ey < n and 0 <= ex < n : # 그래프 넘어가면 무시
            if graph[y][x] < graph[ey][ex]: # 이동 가능한 경우
                # 시작 위치에서 두 번 이동시 2
                # 마지막 위치는 더이상 갈 곳이 없어서 0
                # 상하좌우 이동했을 때 가장 큰 값을 point로 저장
                point = max(point, recur(ey,ex) + 1)
        return 0 # 조건 불만족시 0
    return point

n = int(input()) # 대나무 숲의 크기
graph = [list(int(input().split())) for_ in range(n)] # 대나무 숲의 정보    

# 모든 점을 방문
# 방문한 뒤 이동할 수 있는 모든 경우의 수를 재귀로 구현한다
for y in range(n):
    for x in range(n):
        point = recur(y,x)

 

3번 DP로 구현

dp = n*n의 0 행렬

=> 조건 만족시

dp에 현재의 dp 값 or 상하좌우 이동한 값 중 최대값을 저장

dp[y][x] = max(dp[y][x], recur(ey,ex)+1)

return dp[y][x] 

 

모든 점에서 재귀함수 돌리고

2차원 dp의 최대값+1 출력하기

max(map(max,dp)) + 1

import sys
sys.setrecursionlimit(999999999)
input = sys.stdin.readline

def recur(y,x):
    if dp[y][x] != 0: # dp 재사용하지 않기
        return dp[y][x]
    
    for dy, dx in [[0,-1],[0,1],[-1,0],[1,0]]: # 상하좌우 이동
        # 현재위치 y,x => ey,ex로 좌표이동
        ey = y + dy
        ex = x + dx        
        
        if 0 <= ey < n and 0 <= ex < n : # 그래프 넘어가면 무시
            if graph[y][x] < graph[ey][ex]: # 이동 가능한 경우
                dp[y][x] = max(dp[y][x], recur(ey,ex) + 1)
    return dp[y][x]

n = int(input()) # 대나무 숲의 크기
graph = [list(map(int,input().split())) for _ in range(n)] # 대나무 숲의 정보    
dp = [[0 for _ in range(n)] for _ in range(n)]

for y in range(n):
    for x in range(n):
        recur(y,x)

print(max(map(max,dp)) + 1) # 2차원 최대값 + 1

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/1937_%EC%9A%95%EC%8B%AC%EC%9F%81%EC%9D%B4%ED%8C%90%EB%8B%A4.py