[Algo] 백준 1937 욕심쟁이 판다 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/1937

메모리 : 67896KB

시간 : 588ms

언어 : Java 11

---

코드

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

public class Main {
    static int[][] bamboo;
    static int[][] map;
    static int N, ans, cnt;
    static int[][] vector = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

    static class Node {
        int r, c, b;

        Node(int r, int c, int b) {
            this.r = r;
            this.c = c;
            this.b = b;
        }
    }

    public static <T> void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        bamboo = new int[N][N];
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                bamboo[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        ans = 0;
        cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dfs(i, j, 0);
            }
        }
        System.out.println(ans);
    }

    private static void dfs(int r, int c, int depth) {
        boolean flag = false;
        for (int k = 0; k < 4; k++) {
            int x = r + vector[k][0];
            int y = c + vector[k][1];
            if (x >= 0 && y >= 0 && x < N && y < N) {
                if (bamboo[r][c] < bamboo[x][y]) {
                    flag = true;
                    if (map[x][y] == 0) {
                        dfs(x, y, depth + 1);
                        map[r][c] = Math.max(map[r][c], map[x][y] + 1);
                    } else {
                        map[r][c] = Math.max(map[r][c], map[x][y] + 1);
                    }
                }
            }
        }
        if (!flag) {
            map[r][c] = 1;
        }
        ans = Math.max(map[r][c], ans);
    }
}

풀이

n이 500이기때문에 그냥 완탐을 하게되면 시간초과가 날것이다! 때문에 메모이제이션을 이용해야겠다는 생각이 들었다. 해당 에 판다를 내려놓았을 때 움직일 수 있는 최대 칸을 저장해놓으면, 다른 칸에서 판다가 왔을 때 다시 계산하지 않아도 된다. dfs를 돌면서 더 이상 뱀부를 먹을 수 없을 때 그 칸을 1로 두고, return 하면서 전칸에 +1 한 값을 메모이제이션 하면된다. 이 때 이미 숫자를 가진 칸을 만나면 다음 칸에 갈 필요없이 해당 칸에 적힌 값+1을 해주면 된다.

++ 메모리가 좀 큰데.. 아마 flag를 계속 만들어줘서 그런것 같다. int를 리턴하는 방법으로 바꾸기 귀찮았던..