[코드트리 조별과제] 2차원 배열에서 한칸씩 이동하는 dp

DP문제는 다양하지만 2차원배열에서 한칸씩 전진하면서 그순간마다 최적의 선택을 통해 최종답을 구해나가는 DP가 있다.

 

DP는 어디까지나 전체를 한번에 구한단 생각을 버리고 아주 작은구간 (예를들어 어떤 칸 하나 까지 오는 경우의수) 이런것부터 차곡차곡쌓아나가야 한다.

 

그러면 반복되는 수학식 즉, 점화식이 보이게 된다.

 

다음은 정수 사각형의 최소이자 최대 라는 문제인데

 

사실 문제제목만 보기에는 약간 이상하다. 왜냐하면 최소이자 최대라는게 무슨말일까?

 

최소이자 최대는 즉, 특정 도착지점까지의 경로들은 각각의 경로상의 최솟값이 있는데, 그들중 최대를 구하는것

 

여기서 서브프라블럼은 뭘까? 바로 특정칸까지 도달하기 전까지는 모두 어떤 특정경로의 최소일 것이다.

 

즉, 문제에서 주어진 방향대로 진행해 나가는것은 결국 해당 방향의 역방향에서만 어떤 칸에 도달할 수 있다는 것이고 지금 선택가능한 최솟값들 중 최대를 고르면 된다.

 

아래는 그것을 해결한 상향식코드와 하향식 코드이다.

물론 현재 나아갈려는 지점, 즉 "특정 칸"의 값이 더 최소라면 최솟값을 갱신해야함은 분명하다.

import java.util.*;
import java.io.*;

public class Main {
    static StringTokenizer stk;
    static int n;
    static int[][] map;
    static int[] dy = {0,1};
    static int[] dx = {1,0};
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        map = new int[n][n];
        for(int i = 0;i<n;i++){
            stk =new StringTokenizer(bf.readLine());
            for(int j = 0;j<n;j++){
                map[i][j] = Integer.parseInt(stk.nextToken());
            }
        }

        // DP로 어떻게 해결할 수 있는가?
        // 최소들 중 최대값은 즉, 경로상에 최소값들 끼리 경쟁해서 최대를 구하란 이야기가 된다.
        // 결국 어떤 지점 i, j로 올 수있는 방법은 현재 문제에서 i-1,j 혹은 i, j-1이 되는데
        // 이 때 각각의 최솟값들 중 최대를 선택하는것이 중요하다. 왜냐하면 그래야 "경로상의 최대" 가 되니까
        // 추가적으로 그럼 map[i][j]는 어떻게 비교 할 것인가? 해당 땅을 밟기 위한 조건만 갖추면된다. 즉, 지금까지의 최소이자 최대보다도 더 작다면 갱신인 셈

        int[][] dp =  new int[n][n];
        dp[0][0] = map[0][0];
        for(int i = 1;i<n;i++)
            dp[0][i] = Math.min(map[0][i], dp[0][i-1]);

        for(int i = 1;i<n;i++)
            dp[i][0] = Math.min(map[i][0], dp[i-1][0]);
        
        for(int i = 1;i<n;i++){
            for(int j= 1;j<n;j++){
                dp[i][j] = map[i][j];
                dp[i][j] = Math.min(Math.max(dp[i-1][j], dp[i][j-1]), dp[i][j]);
            }
        }

        System.out.println(dp[n-1][n-1]);

    }
}

 

import java.util.*;
import java.io.*;

public class Main {
    static StringTokenizer stk;
    static int n;
    static int[][] map;
    static int[] dy = {0,1};
    static int[] dx = {1,0};
    static int[][] dp;
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        map = new int[n][n];
        for(int i = 0;i<n;i++){
            stk =new StringTokenizer(bf.readLine());
            for(int j = 0;j<n;j++){
                map[i][j] = Integer.parseInt(stk.nextToken());
            }
        }

        // DP로 어떻게 해결할 수 있는가?
        // 최소들 중 최대값은 즉, 경로상에 최소값들 끼리 경쟁해서 최대를 구하란 이야기가 된다.
        // 결국 어떤 지점 i, j로 올 수있는 방법은 현재 문제에서 i-1,j 혹은 i, j-1이 되는데
        // 이 때 각각의 최솟값들 중 최대를 선택하는것이 중요하다. 왜냐하면 그래야 "경로상의 최대" 가 되니까
        // 추가적으로 그럼 map[i][j]는 어떻게 비교 할 것인가? 해당 땅을 밟기 위한 조건만 갖추면된다. 즉, 지금까지의 최소이자 최대보다도 더 작다면 갱신인 셈
        dp = new int[n][n];
        for(int i = 0;i<n;i++){
            Arrays.fill(dp[i], -1);
        }
        
        dfs(0,0);

        System.out.println(dp[0][0]);
    }
    static int dfs(int y, int x){
        if(dp[y][x] != -1){
            return dp[y][x];
        }

        if(y == n-1 && x == n-1){
            return dp[n-1][n-1] = map[n-1][n-1];
        }
        dp[y][x] = map[y][x];
        int value = 0;
        for(int dir = 0;dir<2;dir++){
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            if(OOB(ny, nx)) continue;
            value = Math.max(value, Math.min(dfs(ny, nx), dp[y][x]));
        }

        return dp[y][x] = value;
    }
    static boolean OOB(int y, int x){
        return y >= n || y < 0 || x >=n || x < 0;
    }
}

 

물론 격자가 그리 크지않고 숫자의 범위도 크지않기에

 

BFS + 파라메트릭 서치 로도 풀 수 있다.

 

import java.util.*;
import java.io.*;

public class Main {
    static StringTokenizer stk;
    static int n;
    static int[][] map;
    static int[] dy = {0,1};
    static int[] dx = {1,0};
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
        map = new int[n][n];
        for(int i = 0;i<n;i++){
            stk =new StringTokenizer(bf.readLine());
            for(int j = 0;j<n;j++){
                map[i][j] = Integer.parseInt(stk.nextToken());
            }
        }

        // 오른쪽 혹은 아래로만 이동하여 우하 끝점에 도달할동안 최솟값의 최대
        // 최솟값의 최대는 즉, 하한경계를 하나 정하고 도달가능한지 검사

        int s = 0;
        int e = 1_000_000;
        int ans = e;
        while(s <= e){
            int mid = (s + e) / 2;
            if(go(mid)){
                s = mid + 1;
            }else{
                e = mid - 1;
                ans = Math.min(e, ans);
            }
        }
        System.out.println(ans);
    }
    static boolean go(int value){
        Queue<int[]> queue =new ArrayDeque<>();
        if(map[0][0] < value) return false;
        boolean[][] v = new boolean[n][n];
        v[0][0] = true;
        queue.add(new int[]{0,0});
        while(!queue.isEmpty()){
            int[] now = queue.poll();
            if(now[0] == n-1 && now[1] == n-1){
                return true;
            }
            for(int dir = 0;dir<2;dir++){
                int ny = now[0] + dy[dir];
                int nx = now[1] + dx[dir];
                if(OOB(ny, nx) || v[ny][nx] || map[ny][nx] < value) continue;
                v[ny][nx] = true;
                queue.add(new int[]{ny, nx});
            }
        }
        return false;
    }
    static boolean OOB(int y, int x){
        return y >= n || y < 0 || x >=n || x < 0;
    }
}