[백준 1937] 욕심쟁이 판다 (자바)

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

1937번: 욕심쟁이 판다

난이도 : 골드 3

 

DFS와 메모이제이션을 이용했습니다. 메모이제이션은 다이나믹 프로그래밍처럼 이전에 계산해 둔 값을 나중에 계속 이용하여 불필요한 계산을 줄일 수 있습니다.

이 문제에서 숲의 최대 크기는 500x500입니다. 메모이제이션을 이용하여 계산의 중복을 막아 시간 초과를 예방했습니다.

 

판다가 이동할 4방향의 칸을 DFS를 통해 계산해줬습니다. 그리고 4방향 중 최댓값에서 1을 더해 현재 판다 위치의 최대 길이를 계산했습니다. 

---

전역 변수

int n = 숲의 크기

int answer = 답(판다의 최대 생존)

int map[][] = 숲에서 대나무의 값

int memo[][] = DFS를 통해 계산한 각 칸에서의 최대 생존 시간

boolean visit[][] = 판다의 방문 여부 확인

int dx[], dy[] = 좌표 이동 방향

함수

void main

전역 변수를 초기화하고 입력을 받습니다. 숲의 모든 칸을 방문하여 DFS를 통해 값을 구합니다.

(dfs 호출)

 

void dfs

현재 칸에서 이동 가능한 방향의 칸을 확인합니다. 만약 방문하지 않았고 현재 칸의 대나무보다 많다면 DFS를 통해 값을 구해줍니다.

현재 칸에서 이동 가능한 칸의 대나무가 현재 칸보다 많다면 가능한 칸들 중 최대 값보다 1 큰 수를 memo 좌표에 저장합니다. 이 값들 중 최댓값을 answer 변수에 저장합니다.

(check 호출)

 

boolean check

이동할 좌표가 옳은 값인지 체크합니다. 범위는 0이상 n미만입니다.