백준 1937 욕심쟁이판다

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

진짜 쉽게 떠올렸는데 잔실수가 많아서 엄청 오래걸린 케이스 ..

메모이제이션 과 dfs를 적당히 섞어서 쓰면 dfs에 고질문제인 stack overflow를 고칠수있다고 생각하였다

그래서 메인로직은 다음과같다.

1. dfs 탐색 (visited check)
2. dfs를 탐색하면서 경로의 값을 메모이 제이션한 배열에 저장해준다.
3. 그리고 메모이제이션한 배열의 최댓값 출력하기

코드는 다음과같다

package DFS;

import java.util.*;
import java.io.*;
public class 욕심쟁이판다 {

	static int[] dx = new int[] {0,0,1,-1};
	static int[] dy = new int[] {1,-1,0,0};
	static int[][] array;
	static int[][] visited;
	static int[][] away;
	static int answer;
	static int tc;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		tc = Integer.parseInt(br.readLine());
		array = new int[tc][tc];
		visited = new int[tc][tc];
		away = new int[tc][tc];
		answer = 0;
		for(int i=0;i<tc;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<tc;j++) {
				array[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0;i<tc;i++) {
			for(int j=0;j<tc;j++) {
				if(away[i][j]==0) {
					find(i,j);
				}

			}
		}
		for(int i=0;i<tc;i++) {
			for(int j=0;j<tc;j++) {
				answer = Math.max(answer, away[i][j]);
			}
		}
		
		System.out.println(answer);
		
	}
	
	
	static int find(int x,int y) {

		away[x][y] = 1; //현재 냠냠
		
		for(int i=0;i<4;i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx<0 || nx >=tc || ny <0 || ny>=tc) continue;
			
			if(array[nx][ny]>array[x][y]) { // 가야될곳을 이동할수있따면
			
				if(away[nx][ny]>0) { //값이 있으면
					away[x][y] = Math.max(away[x][y],away[nx][ny]+1);
					continue;
				}
				away[x][y] = Math.max(away[x][y],find(nx,ny)+1);
			}
			
		}
		return away[x][y];
	}

}

잔실수와.. 그리고 중복처리.. ㅎㅎ;;

아무튼 골드3까지 정복 얼른 bfs로 넘어가자