1937. [Python]욕심쟁이 판다

1. 문제

 

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 256MB
• 재귀
• 깊이우선 탐색
• DP

 

3. 파이썬 코드

 

import sys
# 재귀 제한
sys.setrecursionlimit(10000)
# DFS 실행
def DFS(start):
    global max_value
    global N
    # 온 경로가 방문한 곳일 경우
    if visited[start[0]][start[1]] != 0:
        # 현재 돌아온 경로를 리턴
        return visited[start[0]][start[1]]
    # 시작 값 1로 초기화
    visited[start[0]][start[1]] = 1
    for k in range(4):
        ny = direction[k][0] + start[0]
        nx = direction[k][1] + start[1]
        # 범위 내에 있는 경우
        if 0 <= ny < N and 0 <= nx < N:
            # 다음 가야할 값이 현재 값보다 작은 경우
            if matrix[ny][nx] < matrix[start[0]][start[1]]:
                # 재귀 실행 하며 현재 값이랑 재귀해서 돌아온 값 + 1 한 값을 갱신
                visited[start[0]][start[1]] = max(visited[start[0]][start[1]],DFS((ny,nx))+1)
    # 최종적으로 갱신된 현재 위치값 반환
    return visited[start[0]][start[1]]


input = sys.stdin.readline

N = int(input())

direction = [(0,-1),(-1,0),(0,1),(1,0)]

matrix = []
max_value = 0
visited = [[0] * (N) for _ in range(N) ]

for _ in range(N):
    matrix.append(list(map(int,input().split())))

for i in range(N):
    for j in range(N):
        # 방문하지 않았을 경우 DFS 실행
        if visited[i][j] == 0:
            max_value = max(max_value,DFS((i,j)))

print(max_value)

 

4. 문제를 풀고난 후 생각

 

• 처음 접근 한 방식은 현재 위치에서 큰 값이 있는경우 이동하며 그 위치를 갱신해주는 방식으로 접근을 진행함
• 그러다 보니 결국 새로운 값이 갱신될 경우 그 주위 값들도 모두 갱신됐기 때문에 시간초과가 발생함
• 새로 접근한 방식으로는 현재 위치에서 어디까지 최대 갈 수 있는지를 파악하는 것으로 해결함
• 현재 위치에서 어느 깊이까지 갈 수 있는지 재귀를 통해 접근한 후 초기로 설정한 0 이 아닌 경우 이미 탐색을 했기 때문에 접근하지 않고 바로 return 처리될 수 있도록 함
• return + 1 한 값이랑 현재 위치값 중 max 값을 계속해서 갱신해줌

 

5. 문제를 푸는데 도움이 되는 지식

 

• 깊이 우선 탐색
• 재귀
• DP