백준 1937번 : 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

 

 

 

 

 

문제

• n × n의 크기의 대나무 숲이 있다.
• 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다.
• 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.
• 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다.
• 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.

 

제한사항

• 대나무 숲의 크기 n(1 ≤ n ≤ 500)
• 대나무의 양은 1,000,000보다 작거나 같은 자연수

 

 

 

 

 

풀이

• 그래프 탐색 : DFS

 그래프 내에서 상하좌우에 중 한 곳으로 최대한 이동할 수 있을 때까지 계속 이동해 최대값을 구해야 한다. 그래서 DFS로 탐색을 하기로 했다.

 

 모든 지점 별로 방문할 수 있는 최대 칸 수를 구해야 한다. 매번 모든 지점에 대해 DFS를 한다면 중복되는 부분이 발생해 비효율적이다. 중복적인 탐색을 줄일 방법이 필요하다.

 

 

• DP : 해당 지점을 시작으로 방문할 수 있는 최댓값 저장하기

 그래프와 같은 2차원의 DP 배열에 해당 지점을 시작으로 방문할 수 있는 최댓값 저장한다. 그렇게 되면 이미 방문한 곳에 대해서는 배열에 저장해둔 값을 활용하여 탐색을 줄일 수 있다.

 

 

 DP 배열의 초기값은 0으로, 갱신이 되었다면 0이 아니므로 방문 여부를 알 수 있다. 따라서 별도의 visited 배열을 필요가 없다.

 

 

 

 

어떤 지점(x, y)의 최댓값은 다음 지점(nx, ny)의 + 1이 될 것이다.

dp[x][y] = dfs(nx, ny) + 1

 

 

하지만, 경로별 최대값이 다르므로 탐색할 때마다 해당 지점의 최댓값을 갱신해줘야 한다.

dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + 1)

 

 

 다음과 같이 현재 5의 위치에서 이동할 수 있는 곳은 상단인 12와 왼쪽인 11이다. 상단을 먼저 탐색하게 될 경우 5의 위치의 DP 값은 1+1 = 2가 될 것이다. 하지만 다음에 왼쪽인 11을 탐색하게 된다면 2+1 = 3으로, 먼저 탐색한 2보다 값이 더 크므로 DP 값은 갱신되어야 한다.

 

 

 

 

 

코드

import java.io.*;
import java.util.*;

public class BOJ_욕심쟁이판다 {
	static int N;
	static int[][] graph;
	static int[][] dp;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		graph = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			for(int j = 0; j < N; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dp = new int[N][N];
		
		int max = 0;
		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);
	}

	public static int dfs(int x, int y) {
		if(dp[x][y] != 0) { //이미 방문한적 있음
			return dp[x][y];
		}
		
		dp[x][y] = 1; //초기값
		
		for(int d = 0; d < 4; d++) { //사방탐색
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue; //범위 벗어남
			
			if(graph[x][y] < graph[nx][ny]) {
				dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + 1); //탐색 : 최댓값이 되어야함
			}
		}
		
		return dp[x][y];
	}

}

 

 

 

 

 

 

결과

 

 

 

 

배운점