[백준] 1937 욕심쟁이 판다 / 자바(Java)

문제

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

1937번: 욕심쟁이 판다

 

---

해설

판다가 돌아다닐 수 있는 가장 많은 칸을 찾는 문제입니다.

 

출발점이 정해져 있지 않으니 모든 점을 출발점으로 경로를 확인해야 합니다. 지나온 값의 총 합의 기반으로 경로를 정하지 않기 때문에 2차원 dp배열을 통해 연산량을 줄입니다. 

dp[i][j]는 (i,j) 위치를 지날 때 가장 많이 이동한 횟수

 

dfs를 통해 지도의 모든 위치에서 주변 4방을 탐색 후 자신보다 큰 위치(이동가능한 곳)이 있다면 해당 위치의 dp값+1과 자신의 dp를 비교해 더 높은 값을 저장해 dp를 항상 갱신할 수 있도록 합니다. 만약 주변이 모두 자신보다 작다면 1로 초기화를 해줍니다.

 

모든 계산이 끝난 후 dp의 모든 값중 최대값을 답으로 return합니다.

 

주의점

• 4방 탐색시 자신보다 큰 쪽으로 이동하기 때문에 boolean등을 통한 이전 방문여부를 구별할 필요가 없이 항상 새로운 곳으로 이동합니다.

---

코드

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

public class Main{

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new  InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int map[][] = new int [N][N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int dp[][] = new int[N][N];
		
		int dr[] = {-1,0,1,0};
		int dc[] = {0,1,0,-1};
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				dfs(map, dp, i, j, dr,dc);
			}
		}
		int max=0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				max = Math.max(max, dp[i][j]);
			}
		}
		
		System.out.println(max);
	}
	
	static void dfs(int map[][], int dp[][], int r, int c, int dr[], int dc[]) {
		
		boolean check=true;
		for(int i=0;i<4;i++) {
			int newr = r + dr[i];
			int newc = c + dc[i];
			
			//배열밖인경우
			if(newr<0 || newc<0 || newr>=map.length || newc>=map.length) continue;
			
			// 4방중 나보다 큰 곳이 있는 경우 = 해당 위치+1과 현재의 최대값넣기 
			if(map[newr][newc]>map[r][c]) {
				check=false;
				if(dp[newr][newc]==0) dfs(map, dp, newr, newc, dr, dc);
				dp[r][c] = Math.max(dp[r][c], dp[newr][newc]+1);
			}
		}
		// 4방이 모두 나보다 작은경우 = 1;
		if(check) dp[r][c]=1;
	}
}