[자바] 백준 1937 : 욕심쟁이 판다 / DFS + DP 풀이 / 유사 문제

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

1937번: 욕심쟁이 판다

골드3 난이도, 약 30%의 정답률을 가진 완전탐색 + DP 문제입니다.

---

문제 분석 및 풀이

이 문제를 이해하면 먼저 팬더가 대나무를 4방향으로 먹으러 돌아다닙니다.

팬더는 돌아다닐 때 이전 지역보다 무조건 대나무가 많은 지역으로 가야합니다.

​

이런 조건을 바탕으로 팬더가 먹을 수 있는 (== 팬더가 이동할 수 있는) 지역의 최댓값을 구하는 것이 문제입니다.

​

즉 다른 완전탐색 문제와 다르게 출발점은 정해지지 않습니다.

출발점 또한 완전 탐색으로 시작해주어야합니다.

​

이 문제에서 중요한 포인트는 모든 지역에서 출발했을 때 각 출발 지점에서의 최대 이동할 수 있는 수를 구해야 한다는 점입니다.

​

따라서 저는 DFS로 지역을 탐색하면서 DP를 같이 사용했습니다.

DP는 DFS를 통해 다음 지역으로 갈 때 이전 지역 + 1을 해주고 Math.max로 계속 비교를 해준다면, 그 지점까지 가는데 최대 값을 구할 수 있기 때문입니다.

 

문제 풀이

 

import java.util.Scanner;

public class Main {
    private final static Scanner sc = new Scanner(System.in);
    private static int n;
    private static int[][] map;
    private static int[][] mapOfEatingCount;
    private static int[][] pos = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    private static int answer = 0;

    public static void main(String[] args) {
        initData();
        findAnswer();
        System.out.println(answer);
    }

    private static void initData() {
        n = sc.nextInt();
        mapOfEatingCount = new int[n][n];
        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = sc.nextInt();
            }
        }
    }

    private static void findAnswer() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int count = dfs(i, j);
                answer = Math.max(answer, count);
            }
        }
    }

    private static int dfs(int row, int col) {
        // 이 조건을 안 달아주면 시간초과 발생!, 이미 값이 정해진 곳은 탐색할 필요가 없음
        if (mapOfEatingCount[row][col] != 0) {
            return mapOfEatingCount[row][col];
        }

        mapOfEatingCount[row][col] = 1;

        for (int i = 0; i < pos.length; i++) {
            int nr = row + pos[i][0];
            int nc = col + pos[i][1];

            if (nr >= 0 && nr < n && nc >= 0 && nc < n && map[nr][nc] > map[row][col]) {
                mapOfEatingCount[row][col] = Math.max(mapOfEatingCount[row][col], dfs(nr, nc) + 1);
            }
        }
        return mapOfEatingCount[row][col];
    }
}

 

 

유사 문제

https://blog.naver.com/sosow0212/222997412343

[자바] 백준 2589 : 보물섬 / BFS 풀이