백준 14722 우유도시(DP)

14722번: 우유 도시

BFS + dp table 이용(메모리초과)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

/*
* 동,남쪽으로만 이동하기 때문에 전의 값을 계속 갱신해가면서 값을 더하는 dp문제 같음
*
* 딸기우유를 무조껀 처음에 먹어야한다고 하며 각 자리에 가면 먹거나 안먹거나 선택이 가능하니까
* 2가지 조건 나눠서 점화식 세우면 될 것 같은데??
*
* 1. bfs로 dp table 갱신하는 식으로 했는데 메모리초과
* 2. 그냥 단순 bfs로 했더니 (Queue에 우유 개수를 넘기는 식으로 그냥 가볼까?) 메모리초과
* 3. bfs를 사용하면 안되나?
* */

public class Main {
    static int N;
    static int[] dx = {0,1};
    static int[] dy = {1,0};
    static int[][] board, dp;

    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());

        board = new int[N][N];
        dp = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(bfs()+1);
    }


    public static int bfs(){
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{0,0});

        while(!queue.isEmpty()){
            int[] poll_data = queue.poll();
            int x = poll_data[0];
            int y = poll_data[1];
            for (int i = 0; i < 2; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx<0 || ny<0 || nx>=N || ny>=N)
                    continue;
                if (board[x][y] == 0 && board[nx][ny] == 1){
                    dp[nx][ny] = Math.max(dp[nx][ny], dp[x][y] + 1);
                    queue.add(new int[]{nx,ny});
                }
                else if(board[x][y] == 1 && board[nx][ny] == 2){
                    dp[nx][ny] = Math.max(dp[nx][ny], dp[x][y] + 1);
                    queue.add(new int[]{nx,ny});

                } else if (board[x][y] == 2 && board[nx][ny] == 0) {
                    dp[nx][ny] = Math.max(dp[nx][ny], dp[x][y] + 1);
                    queue.add(new int[]{nx,ny});
                }
                else{
                    dp[nx][ny] = dp[x][y];
                    queue.add(new int[]{nx,ny});
                }

            }
        }
        //System.out.println(Arrays.deepToString(dp));
        return dp[N-1][N-1];
    }

}

 

도저히 풀이 방법이 생각나서 카카시를 했다

 

느낀점은 dp table을 이용하는게 아직 매우 미숙하다는 것이다.

dp table을 세운다는건 알아도 역할을 확실하게 이해하고 있는지에 대해 회의감이 많이 느낀 문제다

 

Point는 총 3개이며

1. 딸기우유를 무조껀 처음 먹어야 한다

=> (0,0)에서 무조껀 딸기우유로 시작하는 경우는 아니기 때문에 조건을 나눠줘야 한다

=> 아예 새로운 -1값으로 현재 우유를 초기화 시켜준다음에 -1일 때 다음 먹어야하는 우유는 0이다 라는 식으로 나타낸다

 

2. dp table 이용

dp[x][y] = Math.max(dp[x][y], cnt);

if (cnt < dp[x][y])
    continue;

(x,y)로 아마 중복으로 검사가 들어올텐데 문제에서 최대한 많은 우유를 마셔야하니까 max로 골라줘야하고 이미 저장된 값보다 작은 값이 들어오면 검사할 필요가 없기 때문에 continue;

 

3.  가지치기

if(board[nx][ny] == nextMilk(now_milk) && dp[nx][ny] < cnt+1){
    dp[nx][ny] = cnt + 1;
    queue.add(new int[]{nx,ny,cnt+1,nextMilk(now_milk)});
}
queue.add(new int[]{nx,ny,cnt,now_milk});

dp[nx][ny] < cnt+1

이 코드를 빼면 메모리 초과 가 100% 난다.

똑같은 원리로 다음 마실 우유를 고르는데 nextMilk의 후보 중에서 dp의 값이 현재 Queue로 넘어온 cnt+1보다 작다면 이또한 고려할 필요가없는 문제다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main_14722 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        int[][] board = new int[N][N];
        int[][] dp = new int[N][N];
        Queue<int[]> queue = new ArrayDeque<>();

        int[] dx = {1,0};
        int[] dy = {0,1};


        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        if (board[0][0] == 0){
            dp[0][0] = 1;
            queue.add(new int[]{0,0,1,0});
        }
        else{
            queue.add(new int[]{0,0,0,-1});
        }

        while(!queue.isEmpty()){
            int[] poll_data = queue.poll();
            int x = poll_data[0];
            int y = poll_data[1];
            int cnt = poll_data[2];
            int now_milk = poll_data[3];
            dp[x][y] = Math.max(dp[x][y], cnt);

            if (x==N-1 && y==N-1)
                continue;
            if (cnt < dp[x][y])
                continue;

            for (int i = 0; i < 2; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx<0 || ny<0 || nx>=N || ny>=N)
                    continue;
                if(board[nx][ny] == nextMilk(now_milk) && dp[nx][ny] < cnt+1){
                    dp[nx][ny] = cnt + 1;
                    queue.add(new int[]{nx,ny,cnt+1,nextMilk(now_milk)});
                }
                queue.add(new int[]{nx,ny,cnt,now_milk});
            }
        }

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




        }
        public static int nextMilk(int cur) {
            if(cur==-1) {
                return 0;
            } else if(cur==0) {
                return 1;
            } else if (cur==1) {
                return 2;
            } else {
                return 0;
            }
        }




    }