[백준 17070번][Java] 파이프 옮기기 1 - DP, 메모이제이션

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

문제 자체는 DFS를 이용한 전형적인 길찾기 문제와 비슷했습니다.

 

주의할 점이라면 다음 좌표로 이동할 때, 주변에 장애물이 없는지 살펴야 합니다.

세로나 가로로 이동할 때는 상관이 없지만 대각으로 이동하는 경우에 이동하려는 좌표 위, 왼쪽이 모두 빈 공간이여야하기 때문입니다.

 

 

 

package backjoon.dp.p17070;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[][] room;
    static int[][][] cache;

    public static void main(String[] args) throws IOException {
        InputReader reader = new InputReader("testcase.txt");
//        InputReader reader = new InputReader("testcase.txt");
        N = reader.readInt();
        room = new int[N][N];
        cache = new int[N][N][3];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                Arrays.fill(cache[i][j], -1);
            }
        }

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

        int ret = movePipe(0,1,0);
        System.out.println(ret);

    }
    static int[] dr = {0,1,1}; //오른쪽, 오른쪽 대각, 아래
    static int[] dc = {1,1,0};
    public static int movePipe(int row, int col, int state) {
        if(row == N-1 && col == N-1) return 1;
        if(cache[row][col][state] != -1) return cache[row][col][state];

        int ret = 0;
        //파이프의 초기 상태가 가로 방향인 경우
        for (int i = 0; i < 3; i++) {
            int nextRow = row + dr[i];
            int nextCol = col + dc[i];

            boolean whenHorizon = state == 0 && i <= 1;
            boolean whenDiagonal = state == 1;
            boolean whenVertical = state == 2 && i >= 1;

            if(isRange(nextRow, nextCol) && hasSpace(nextRow, nextCol, i)) {
                if(whenHorizon) ret += movePipe(nextRow, nextCol, i);
                if(whenDiagonal) ret += movePipe(nextRow, nextCol, i);
                if(whenVertical) ret += movePipe(nextRow, nextCol, i);
            }

        }
        return cache[row][col][state] = ret;
    }
    /*

     */
    private static boolean hasSpace(int row, int col, int state) {
        if(state == 0 || state == 2) {
            return room[row][col] == 0;
        }
        int[] dr = {-1,0,0}; int[] dc = {0,0,-1};
        for (int i = 0; i < 3; i++) {
            int nextRow = row + dr[i];
            int nextCol = col + dc[i];
            if(room[nextRow][nextCol] != 0) return false;
        }
        return true;
    }

    private static boolean isRange(int row, int col) {
        if(row < 0 || row >= N || col < 0 || col >= N) return false;
        return true;
    }

}
class InputReader {
    private BufferedReader br;

    public InputReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public InputReader(String filepath) {
        try {
            br = new BufferedReader(new FileReader(filepath));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public List<Character> readLineIntoCharList() throws IOException {
        List<Character> l = new ArrayList<>();
        while(true) {
            int readVal = br.read();
            if(readVal == '\n' || readVal == -1) break;
            l.add((char)readVal);
        }
        return l;
    }

    public boolean ready() throws IOException {
        return br.ready();
    }

    public String readLine() throws IOException {
        return br.readLine();
    }
    public int readInt() throws IOException {
        return Integer.parseInt(readLine());
    }
    public Long readLong() throws IOException {
        return Long.parseLong(readLine());
    }
}