[백준 / BOJ] 1937 욕심쟁이 판다

문제

출처 : www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

N*N크기의 대나무 숲에있는 판다는 한 지역의 대나무를 다 먹으면 상하좌우중 한 방향으로 움직일수있다.

단, 이때 움직인곳은 전 지역보다 대나무가 많아야한다.

 

풀이

9달전에 풀다가 틀렸었는데, 알고리즘 공부를 더 하고서야 맞췄다.

(9달전에는 바텀업 구현을 못해서 풀지 못했음)

 

DFS와 DP를 합친 문제다. 

 

1. (i ~ N) (j ~ N) 까지 전부다 돌려준다.

2. (i,j)점에서 시작해서 DFS를 돌려준다.

3. DFS를 돌면서 해당 (i,j)지점에서 갈수있는 최대 날짜를 DP배열에 업데이트 해줘야한다.

4. 만약 이미 i,j에 값이 들어가있다면, 그 정점에서 시작해서 갈수있는 최대 날짜만큼 간것이니 더이상 탐색하지않고 종료한다.

 

위를 반복하면 각 정점에서 갈수있는 최댓값이 갱신된다. 이를 찾아서 출력하면 답.

 

위의 3번을 구현하기 위해선 바텀업 방식으로 DFS를 돌려야한다. (해당 정점에서 갈수있는 최댓값을 갱신해줘야하기 때문.. 9개월 전에는 이걸 구현못했어서 해맸었다)

 

return dp[Y][X] = 1 + max(max(max(max(go(Y, X, Y+1, X),go(Y, X, Y, X+1)),go(Y, X, Y-1, X)),go(Y, X, Y, X-1)),dp[Y][X]);

소스코드중 일부이다. 

한번 들어갈때마다 1씩 더해주는걸 볼수있다.

 

바텀업 방식 그림..

위 그림을 보면 4까지 탐색한후 재귀가 종료됐을때, 1씩 더해주며 올려주는걸 볼수있다.

이렇게 되면 결국, 4에는 0, 3에는 1, 2에는 2, 1에는 3이 저장될것이다...

 

소스코드

https://github.com/devxb/JJUNalgo/tree/master/1937%20%EC%9A%95%EC%8B%AC%EC%9F%81%EC%9D%B4%20%ED%8C%90%EB%8B%A4

devxb/JJUNalgo