n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.
이 판다의 사육사는 이런 판다를 대나무 숲에 풀어놓아야 하는데, 어떤 지점에 처음에 풀어놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.
지문에 있는 내용 자체가 해석이 그리 어렵지는 않다. (1, 1) 지점부터 (n, n) 지점까지 모든 점을 돌며 판다의 움직임을 DFS로 시뮬레이션 하자.
이때, 이동한 거리를 다른 n x n 크기의 배열에 저장하여 DP 테이블로 사용하는 것이 포인트이다.
이제 간단한 예시를 하나 보자.
오른쪽 n x n 배열을 "그 지점부터 추가로 이동 가능한 거리의 최댓값"을 저장하는 용도로 사용했다. 만약 BFS를 이용한다면 이 방법이 제한된다.
(BFS는 시작 지점부터 이 지점까지의 최솟값을 구하는 용도로는 DFS보다 적합하다, 왜 그런지 바로 납득이 안된다면 시간을 조금 내어 생각해 보거나 댓글로 문의하자.)
문제를 풀 콘셉트를 결정했다면 이제 규칙을 세울 수 있다.
규칙 A : (1,1) 지점부터 (n, n) 지점까지 모든 지점을 순회하며 DFS를 한다, 이때 이동 가능 지점은 자기 자신보다 더 큰 값이 있는 칸이다.
규칙 B : 만약 DFS 도중 DP 테이블에 초기값 (= 0) 이 아닌 값을 만났다면, 그 시점에서 탐색을 종료한다. 종료 값은 그 지점의 값이다.
규칙 C : 만약 DFS 도중 더 이상 이동 불가능하다면, 그 시점에서 탐색을 종료한다. 종료 값은 1이다.
규칙 D : DFS 탐색이 종료되었다면 탐색 경로를 되돌아온다.(= 하나씩 pop 한다)
규칙 D-1 : 이때 DP 테이블에 종료 값을 1개씩 늘려가며 넣는다
규칙 D-2 : 만약 DP 테이블에 넣을 값 보다 기존 값이 더 크다면 종료 값을 기존 값으로 변경한다.
이 규칙을 가지고 문제에서 주어진 예제 입력을 풀어보자.
(규칙 A)에 의해 탐색을 시작하지만, 바로 끝나버린다. (= 인접한 칸 중 14보다 더 큰 값이 없음) (규칙 C)에 의해 종료 값은 1이 되며 (규칙 D)에 의해 시작 지점까지 돌아가며 종료 값을 하나씩 증가시켜 넣어주어야 하지만, 시작 지점 = 끝 지점이므로 그대로 1을 넣고 끝낸다.
그다음 칸에서 탐색을 시작한다.
14가 더 크기 때문에 탐색이 가능하다. 하지만 (규칙 B)에 의해 이미 탐색된 값은 그 시점에서 탐색을 멈춘다. 종료 값은 1이 되고, 한 칸 뒤로 돌아온 9 지점에서는 종료 값이 2가 된다. (1씩 늘어난다)
즉 9 지점에는 2를 넣을 수 있다.
그런데 9 지점에서는 14로만 갈 수 있는 것은 아니다. 11방향으로 탐색을 진행하면 15까지 총 3칸을 올 수 있다.
한 칸씩 되돌아오며 값을 값을 넣어준다. 이때 9 지점에서 기존 값과 새로운 값 이 충돌하는데, 이경우 (규칙 D-2)에 의해 더 큰 값인 3을 선택한다.
이러한 방식으로 탐색을 계속 진행한다.
이 부분은 BFS처럼 보일 수 있으나, 이미지의 시간 관계상 많은 생략을 한 것이다. 실제로 동작은 DFS로 할 수 있으며 이경우엔 더 큰 값인 3 (2+1) 이 5 자리에 들어가는 것이 맞다.
모든 탐색이 끝난 뒤, 최종적으로 완성된 오른쪽 DP 테이블에서 가장 큰 값을 찾아 출력하면 된다.
