[BOJ] 1937 - 욕심쟁이 판다

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

난이도: 골드 3

사용언어: JAVA

 

풀이

이 문제는 DFS와 다이나믹 프로그래밍을 함께 이용하여 해결할 수 있습니다. dfs에 관한 기본적인 내용은 아래 문제의 풀이에서 볼 수 있습니다.

 

jooona.tistory.com/65

[BOJ] 1303 - 전쟁 - 전투

다이나믹 프로그래밍은 이차원 배열인 dp[][]를 이용합니다.

 

다이나믹 프로그래밍을 위한 배열에는 해당 칸에 도달했을 때 생존할 수 있는 최대 일수를 저장합니다. DFS를 통해 더 많은 대나무가 있는 위치를 찾아 이동하고, 해당 칸의 상하좌우에 있는 칸의 dp에 정보가 이미 존재하면 그 정보를 가져다 쓰고, 그렇지 않다면 DFS를 통해 해당 칸으로 이동하는 형태입니다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Main {
    static int[][] arr;
    static int[][] dp;
    static int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 상하좌우
 
    public static int dfs(int x, int y) {
        int i;
        int nx, ny;
        int[] val = new int[4]; // 상하좌우의 dp 값을 저장할 배열
        for (i = 0; i < 4; i++) { // 상하좌우가 모두 자신보다 대나무가 적은, 즉 더 이상 갈 곳이 없는 칸인지를 확인
            if (arr[x + d[i][0]][y + d[i][1]] != 0 && arr[x + d[i][0]][y + d[i][1]] > arr[x][y])
                break;
            if (i == 3) {
                dp[x][y] = 1;
                return 1; // 만약 더 갈 수 있는 곳이 없는, 마지막 칸이라면, 해당 칸에 도달하면 1일만 생존할 수 있다.
            }
        }
 
        for (i = 0; i < 4; i++) {
            nx = x + d[i][0];
            ny = y + d[i][1];
            if (arr[nx][ny] != 0 && arr[nx][ny] > arr[x][y] && dp[nx][ny] != 0) {
                val[i] = dp[nx][ny] + 1; // 만일 이동하고 싶은 칸을 이미 앞에서 검사하여 dp를 구해놓았다면 1만 더해서 사용
            } else if (arr[nx][ny] != 0 && arr[nx][ny] > arr[x][y] && dp[nx][ny] == 0) {
                val[i] = dfs(nx, ny) + 1; // 아직 검사하지 않은 칸이라면 재귀로 dfs 수행
            }
        }
       Arrays.sort(val); // 상하좌우의 dp 값을 소팅해서
        dp[x][y] = val[3]; // 가장 큰 값 (가장 오래 생존할 수 있는 일수)을 dp 배열에 넣어준다.
        return val[3];
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N + 2][N + 2];
        dp = new int[N + 2][N + 2];
        int i, j;
        int max = Integer.MIN_VALUE;
        StringTokenizer st;
        for (i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (j = 1; j <= N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for (i = 1; i <= N; i++) {
            for (j = 1; j <= N; j++) { // 가장 좌측 상단 칸부터 dfs 수행
                if (dp[i][j] == 0) // 해당 칸에 dp가 아직 작성되지 않았다면
                    dp[i][j] = dfs(i, j); // dfs 호출
            }
        }
 
        for (i = 1; i <= N; i++) {
            for (j = 1; j <= N; j++) {
                max = Math.max(max, dp[i][j]); // 최종적으로 가장 큰 값을 찾아서
            }
        }
        bw.write(String.valueOf(max)); // 출력
        bw.flush();
        br.close();
        bw.close();
    }
}