백준_욕심쟁이 판다_1937[Java]

문제 

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

1937번: 욕심쟁이 판다

 

흐름 

완전탐색과 동적계획법, 메모이제이션을 이용하면 된다. 

이중 for문을 이용해 숲에서의 모든 자리를 탐색한다. 여기서 탐색은 최대로 살 수 있는 일수를 반환하는 과정이다.

탐색한 결과값을 기억해둔다. (메모이제이션 : visit 배열)

이미 방문한 위치는 visit배열에서 값이 0이 아닐 것, 따라서 0인 경우에는 바로 visit배열에 담긴 값을 반환하여 최대값을 찾는다.

 

기저사례 :

현재의 판다 자리에서 상하좌우로 움직였을 경우 숲 경계 밖으로 나간다거나 

현재 자리보다 더 많은 양의 대나무를 가진 상하좌우 위치가 존재하지 않았을 때이다. 

 

코드

import java.util.Scanner;

public class Main {
	static int n;
	static int[][] forest;
	
	static int K = 1;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		forest = new int[n][n];
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				forest[i][j] = sc.nextInt();
			}
		}
		
		int[][] visit = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				K = Math.max(K,solution(visit, i, j));
			}
		}
		
		System.out.println(K);
		
		sc.close();
	}
	
	// 왼 위 오 아 
	static int[] dx = {0, -1, 0, 1};
	static int[] dy = {-1, 0, 1, 0};
	
	private static int solution(int[][] visit, int curX, int curY) {
		int nextM = curX;
		int nextN = curY;
		
		if(visit[curX][curY] != 0) {
			return visit[curX][curY];
		}
		
		visit[curX][curY] = 1;
		// visit[curX][curY] == 0
		for(int i = 0; i < 4; i++) {
			nextM += dx[i];
			nextN += dy[i];
			
			if(nextM >= n || nextN >= n || nextM < 0 || nextN < 0) {
                nextM -= dx[i];
				nextN -= dy[i];
				continue;
			}
			
			if(forest[curX][curY] < forest[nextM][nextN]) {
				visit[curX][curY] = Math.max(visit[curX][curY], solution(visit, nextM, nextN)+1);
				
			}
			nextM -= dx[i];
			nextN -= dy[i];	
		}
		
		return visit[curX][curY];
	}

}

 

참고 

- 내가 주로 참고한 블로그 (초심플)

https://lmcoa15.tistory.com/58

백준 1937번 - 욕심쟁이 판다

 

- 이 분은 생각의 과정과 풀이가 상세히 적어두셨다. 나와 방법이 아주 쬐금 다르다.

http://blog.naver.com/occidere/221011856706

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