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

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

1937번: 욕심쟁이 판다

[문제]

 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.

 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

 

[입력 조건]

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

 

[코드]

import java.util.*;

public class BaekJoon_1937 {
	static int n,max=0;
	static int[][] map, dp;
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,-1,0,1};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		map=new int[n][n];
		// dp[i][j]에는 해당 칸에서 출발하여 판다가 방문할 수 있는 최대 칸수 저장
		dp=new int[n][n]; 
		
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				map[i][j]=sc.nextInt();
		
		// 모든 지점을 시작점으로 바꿔가며 최대 방문 칸수 구하기
		for(int i=0;i<n;i++) 
			for(int j=0;j<n;j++) 
				max=Math.max(max,dfs(i,j));
			
		System.out.println(max);
	}
	
	static int dfs(int x, int y) {
		if(dp[x][y]!=0) // dp에 저장된 값이 있을 경우 값 반환
			return dp[x][y];
		
		dp[x][y]=1; // (x,y) 칸을 포함해야 하기 때문에 1로 초기화
		// 상,하,좌,우 탐색
		for(int i=0;i<4;i++) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			// 이동할 칸이 범위 내에 있고,
			if(nx>=0&&nx<n&&ny>=0&&ny<n) {
				// 이동할 칸의 대나무가 현재 칸보다 많다면 이동 가능
				if(map[nx][ny]>map[x][y]) {
					/*
					 * dp 값은 현재 칸의 값과 상,하,좌,우 중 방문할 수 있는 
					 * 칸 수가 가장 많은 값 + 1(x,y 칸으로 이동) 중 큰 값을 선택한다. 
					 */
					dp[x][y]=Math.max(dfs(nx,ny)+1,dp[x][y]);
				}
			}
		}
		
		return dp[x][y];
	}
}

 

[고찰]

 처음에는 모든 지점을 시작점으로 삼으면서 DFS로 가능한 모든 경로를 탐색하는 방식으로 접근했지만 시간초과 결과를 받아 다른 해결방법을 찾아야 했다. 하지만 다른 아이디어가 떠오르지 않아 다른 사람을 코드를 참고해보니 "DFS+DP" 문제였다. 

 배열의 각 지점을 시작으로 DFS 함수를 실행하여 시작 지점으로 부터 판다가 이동할 수 있는 최대 거리를 찾는 방식으로 해결할 수 있었다. dp[x][y]의 값은 상, 하, 좌, 우 중 이동할 수 있는 칸 수 가 가장 많은 값을 찾아야 하기 때문에 점화식은 dp[x][y]=Math.max(dfs(nx,ny)+1,dp[x][y])와 같이 구성할 수 있다. +1을 한 이유는 상, 하, 좌, 우 칸에서 (x, y) 칸으로 이동해야 하기 때문이다. 

 

 DP 유형의 문제를 풀어본지 시간이 좀 지나 평소에 자주 풀어보던 DFS를 사용할 생각밖에 하지 못한것 같다. 문제에 접근하는 시각을 좀 더 넓혀야겠다는 생각을 하게됐다.