1937 – Nextra

욕심쟁이 판다

https://www.acmicpc.net/problem/1937 (opens in a new tab)

내 풀이

내 첫 번째 풀이는 visited[ny][ny] = false 이런식으로 하는 바람에 안됐다. 하지만 변경 후에도 31%에서 시간초과가 났다.
DP도 처음에 구상하는 단계에서 가장 높은 곳을 기준으로 그 다음 높은 곳, 그 다음 높은 곳을 찾아가면서 DP 풀이를 생각했는데 뭔가 구현 과정과 그 풀이가 맞다는 증명 과정이 너무 어려워서 40분 제한 안에 못 풀것 같아서 포기했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static Integer[][] DIRECTION = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
    static boolean[][] visited;
    static Integer[][] MAP;
    static int N;
    static int MAX = 1;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        MAP = new Integer[N][N];
        visited = new boolean[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());
            }
        }
 
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                visited[r][c] = true;
                int[] point = {r, c};
                dfs(point, 1);
                visited[r][c] = false;
            }
        }
        System.out.println(MAX);
    }
 
    public static void dfs(int[] point, int cnt) {
        for (Integer[] d : DIRECTION) {
            int x = point[0];
            int y = point[1];
 
            int dx = d[0];
            int dy = d[1];
 
            int nx = x + dx;
            int ny = y + dy;
            boolean validRange = -1 < nx && nx < N && -1 < ny && ny < N;
            if (!validRange) continue;
            boolean canMove = !visited[nx][ny] && MAP[x][y] < MAP[nx][ny];
            if (canMove) {
                visited[nx][ny] = true;
                int[] np = {nx, ny};
                int ncnt = cnt + 1;
                dfs(np, ncnt);
                visited[nx][ny] = false;
            }
        }
        MAX = Math.max(cnt, MAX);
    }
}

GPT 풀이

현재 시작하는 지점은 다음 지점의 +1이기 때문에 이러한 특성을 이용해서 DP로 풀이한 경우이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int[][] DIRECTION = {{1, 0}, {-1, 0}, {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));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dp = new int[N][N]; // 메모이제이션 배열 추가
 
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                max = Math.max(max, dfs(i, j)); // 각 위치에서 dfs 수행
            }
        }
 
        System.out.println(max);
    }
 
    public static int dfs(int x, int y) {
        if (dp[x][y] != 0) return dp[x][y]; // 이미 방문한 위치면 저장된 값 반환
 
        dp[x][y] = 1; // 시작 위치는 무조건 1칸 방문 가능
        for (int[] d : DIRECTION) {
            int nx = x + d[0];
            int ny = y + d[1];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N && map[x][y] < map[nx][ny]) {
                dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + 1); // 다음 위치 탐색 후 최대 칸 수 갱신
            }
        }
 
        return dp[x][y];
    }
}

Number of Island 구간 나누기 2