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

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

1937번: 욕심쟁이 판다

풀이

위 문제는 dfs와 bfs를 이용해서 풀 수 있는 것처럼 보이지만 dp를 이용하지않으면 시간초과가 발생한다.

메모제이션, 즉 dp를 이용해서 실행시간을 단축시켜야한다.

 

출발지가 정확하게 명시되어 있지 않은 문제이기 때문에 bfs를 이용해야하고, 메모제이션을 이용해서 해당 과정에서의 시간을 단축시키면 된다.

 

우선 2차원 배열을 생성하고 임의의 출발지에서 상하좌우로 움직이면서 최대한 많은 칸을 이동한 횟수를 구하면 된다.

예제 1번을 보면서 살펴보겠다.

 

1. 먼저 (0, 0)의 14부터 시작한다. 욕심쟁이 판다는 현재 위치에 있는 대나무보다 더 많은 대나무를 원한다. 그렇기 때문에 어디에도 이동할 수 없다.

2. 다음은 (0, 1)의 9를 살펴보겠다. 상하좌우에서 더 큰 값을 찾아서 이동하면 된다. 오른쪽으로 한 칸, 아래로 2칸을 내려갈 수 있다.

dfs를 이용했기 때문에 이동할 곳까지 들어가서 dp[x][y]를 '1'로 초기화해준다. 위 그림으로 보면 dp[0][2] 와 dp[2][1]가 '1'로 초기화될 것이다.

더 이상 이동할 곳이 없는 곳 까지 내려간 후에 '1'로 초기화 후 리턴을 반복해주면서 다시 출발지로 돌아온다. 위 상황에선 아래에서 올라온 '3'과 오른쪽에서 온 '2'가 비교가 될 것이다. 출발지까지 돌아온 값 중에 더 큰 값으로 초기화해주면 된다. dp[0][1] = 3이 된다.

 

위의 과정을 반복하면서 최대한의 이동 횟수를 구하면 된다. 

 

<최종코드>

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

public class Main {
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int[][] map, dp;
    static int N;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        N = Integer.parseInt(br.readLine());
        map = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
		
        int ans = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                ans = Math.max(ans, dfs(i, j));
            }
        }
		
        System.out.println(ans);
    }
	
    public static int dfs(int x, int y) {
        // 값이 있다면 바로 넘겨줌 (메모제이션)
        if (dp[x][y] != 0) return dp[x][y];
		
        dp[x][y] = 1; // 초기화
		
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
			
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
			
            if (map[x][y] < map[nx][ny]) {
                dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + 1);
            }
        }
		
        return dp[x][y];
    }
}