BOJ_1937_욕심쟁이 판다 (Java)

[Gold III] 욕심쟁이 판다 - 1937

문제 링크

성능 요약

메모리: 37428 KB, 시간: 456 ms

분류

깊이 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색

제출 일자

2025년 1월 8일 14:42:05

문제 설명

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

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

입력

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

출력

첫째 줄에는 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.

문제 풀이

간단한 dfs, 메모이제이션(백트래킹) 문제.

문제 접근

DFS와 DP(동적 계획법)를 결합하여 해결하는 대표적인 문제다. 판다가 현재 위치에서 이동할 수 있는 최대 칸 수를 구하기 위해, 각 위치에서 시작했을 때의 최대 이동 가능 거리를 메모이제이션하는 방식을 사용한다.

핵심 로직

• DP 배열의 의미
  • dp[r][c]: (r,c) 위치에서 시작했을 때 이동할 수 있는 최대 칸 수 초기값 0은 아직 계산하지 않은 상태를 의미
• DFS 탐색 과정
  • 현재 위치에서 상,하,좌,우 네 방향을 탐색
  • 다음 위치의 대나무가 현재 위치보다 많은 경우에만 이동
  • 이동할 때마다 이전 위치의 최대 이동 칸 수 + 1을 계산

• 메모이제이션

  • 이미 계산된 위치(dp[r][c] ≠ 0)는 재계산하지 않고 저장된 값 사용
  • 이를 통해 중복 계산을 방지하고 시간 복잡도를 크게 줄임

• 시간 복잡도

  • O(N²): 모든 위치에 대해 한 번씩만 계산

구현 시 주의사항

• 초기값 설정

  • 각 위치에서 최소 1칸은 이동 가능하므로 dp[r][c] = 1로 초기화

• 경계 조건 처리

  • 배열 범위를 벗어나지 않도록 체크

• 최댓값 갱신

  • 모든 시작점에 대해 DFS를 수행하며 전체 최댓값 갱신

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int N, board[][], dp[][], dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		board = new int[N][N];
		dp = new int[N][N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int res = 1;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				res = Math.max(res, dfs(i, j));
			}
		}
		bw.write(String.valueOf(res));
		bw.flush();
		bw.close();
		br.close();
	}

	private int dfs(int r, int c) {
		if(dp[r][c] != 0) return dp[r][c];
		
		dp[r][c] = 1;
		
		for(int k=0; k<4; k++) {
			int nr = r + dr[k];
			int nc = c + dc[k];
			
			if(nr >= 0 && nr < N && nc >= 0 && nc < N) {
				if(board[nr][nc] > board[r][c]) dp[r][c] = Math.max(dp[r][c], dfs(nr, nc) + 1);
			}
		}
		return dp[r][c];
	}
}