[백준] 17070번 : 파이프 옮기기 1

17070번: 파이프 옮기기 1

---

[DFS + 동적 프로그래밍]

가로

세로

대각선

 

 그림처럼 다음 파이프를 놓는 것은 현재 파이프가 어떻게 놓여져 있는지에 의존한다. 그래서 dp[n][n][3]이라는 배열을 사용했고, dp[n][n][0]은 가로로 놓여져 있을 때, dp[n][n][1]은 대각선, dp[n][n][2]는 세로로 놓여져 있을 때의 경우의 수를 나타낸다.

 그리고 대각선의 경우 대각선을 나타내는 좌표 뿐 아니라, 좌측, 상측 모두 빈공간이어야 함을 명심해야한다. 이제 2차원 배열에서 DFS를 이용해 경우의 수를 구하면 된다. dp[][][]는 -1로 초기화 시키고, 정점을 처음 방문하면 0으로 세팅하고 (n, n) 정점에 도달할 수 있으면 1을 반환하도록 한다. 만약 같은 정점을 다시 DFS가 호출한다면, 저장되어있는 값을 반환하는 메모제이션을 사용한다.

 

DFS메서드는 좌표와 type을 인자로 갖으며, type에 따라 탐색하는 범위가 달라진다.

# Code </>

public class Main {

    static int n;
    static int[][] map = new int[17][17], dp[] = new int[17][17][3];
    static int[] Y = {0, 1, 1}, X = {1, 1, 0};

    static int DFS(int y, int x, int type){

        if(y == n && x == n)
            return 1;

        if(dp[y][x][type] != -1) return dp[y][x][type];

        dp[y][x][type] = 0;

        int v1, v2;

        if(type == 0) {
            v1 = 0;
            v2 = 1;
        }
        else if(type == 1){
            v1 = 0;
            v2 = 2;
        }
        else{
            v1 = 1;
            v2 = 2;
        }

        for (int a = v1; a <= v2; a++) {
            int ny = y + Y[a];
            int nx = x + X[a];

            if(ny > n || nx > n || map[ny][nx] == 1) continue;
            if(a == 1 && (map[ny-1][nx] == 1 || map[ny][nx-1] == 1)) continue;

            dp[y][x][type] += DFS(ny, nx, a);
        }

        return dp[y][x][type];
    }

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

        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                Arrays.fill(dp[i][j], -1);
            }
        }

        System.out.println(DFS(1, 2, 0));
    }
}