[백준] 1937_욕심쟁이 판다

김태민·2022년 5월 23일
0

알고리즘

목록 보기
71/77

mingssssss

1. 문제

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

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

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

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

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

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.io.InputStreamReader;

public class Main {
	
	static int N;
	static int[][] list;
	static int[][] dp;
	static int answer;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		list = 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++) {				
				list[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// 리스트 // dp 배열 입력 종료
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {				
				answer = Math.max(answer, dfs(i, j));
			}
		}
		
		System.out.println(answer);
		
		// 출력
//		for (int i = 0; i < N; i++) {
//			for (int j = 0; j < N; j++) {
//				System.out.printf("%d ", dp[i][j]);
//			}
//			System.out.println();
//		}
		
	}
	
	private static int dfs (int r, int c) {				
		
		// 해당 좌푯값이 0이 아니라면 현재 좌푯값 리턴
		if (dp[r][c] != 0) {
			return dp[r][c];
		}
		
		// 해당 좌표에서 1년부터 살기 시작하므로
		dp[r][c] = 1;
		
		for (int i = 0; i < 4; i++) {
			
			int nextX = r + dx[i];
			int nextY = c + dy[i];
			
			if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) {
				continue;
			}
			
			if (list[nextX][nextY] > list[r][c]) {
							
				dp[r][c] = Math.max(dp[r][c], dfs(nextX, nextY) + 1);
//                dfs(nextX, nextY);
			}

		}
		
		return dp[r][c];
	}

}

3. 리뷰

임의의 좌푯값에서 갈 수 있는 최대의 거리를 구하는 문제이다.

dfs로 풀어야 하지만 그냥 풀면 시간초과나기 딱 좋은 문제여서

DP를 이용해서 풀어야 한다.

일단 모든 좌표에서 갈 수 있는 거리를 구해야 하기 때문에, 이중 for문으로

모든 좌푯값을 탐색한다.

dfs에는 DP를 활용하여 해당 좌푯값이 0이 아니라면, 이미 그 자리에서

갈 수 있는 최대 거리가 구해져 있는 경우이므로, 그 값을 return하면 된다.

그게 아니라면, 처음 방문하는 것이므로 해당 dp값은 판다가 1년부터 살기 시작하므로

1로 초기화 해주고 진행한다.

다음 탐색할 좌표의 대나무 수가 현재 탐색하는 좌표의 대나무 수보다 많다면,

dp의 현재 값은 dp의 현재값과 다음 탐색할 좌표의 dfs 값에 1을 더한 값과 비교해서

max값을 저장해준다.

다른 부분은 구현하기 어렵지 않았는데, dp의 현재 값에 dfs를 탐색한 값의 max값에

1을 더하는 부분을 생각하기 어려웠다. 익혀두면 자주 쓸 방법인 것 같다.

profile
어제보다 성장하는 개발자

0개의 댓글