[백준 17069] 파이프 옮기기2 java

문제

파이프를 연결해서 (N-1,N-1)칸 까지 갈 수 있는 경우의 수를 세는 문제.
파이프는 세로, 가로,대각선으로만 둘 수 있다.
세로 파이프는 세로, 대각선으로만 이을 수 있다.
가로 파이프는 가로, 대각선으로만 이을 수 있다.
대각선은 가로,세로,대각선 모두 가능하다.

풀이 방법

i,j 좌표로 올 수 있는 방법을 저장하는 3차원 dp배열을 만들어서 저장 한다.
파이프 모양에 따라서 방법의 수가 달라지기 때문에 3차원으로 만들어서 가로,세로,대각선일 경우를 각각 따져야 한다.

(i,j)에 두는 파이프 모양에 따라 경우의 수를 구한다.

1. 가로로 둘 경우 - 왼쪽 칸에 가로로 둔 경우, 대각선으로 둔 경우만 가능 : (i,j-1)의 가로 방법 수 + (i,j-1)의 대각선 방법의 수
2. 세로로 둘 경우 - 윗칸에 세로로 둔 경우, 대각선으로 둔 경우만 가능 : (i-1,j) 세로 방법 수 +(i-1,j)의 대각선 방법 수
3. 대각선으로 둘 경우 : (i-1,j-1)에 둘 수 있는 모든 경우

최종적으로 map[n-1][n-1] 의 모든 경우들을 더해 주면 답이 된다.

코드

• 파이프가 초기에 가로로 놓여 있기 때문에 0번째 행은 가로로 밖에 둘 수 없다. 그래서 미리 가로 방향만 1로 초기화 시켜주었다.
• map에 벽이 놓여져 있다면 파이프를 둘 수 없다.
  • 따라서 map(i,j)가 벽이라면 파이프를 두지 않는다.
  • 대각선으로 파이프를 둘 경우 상,좌 칸에도 벽이 없어야 가능하므로 체크해주어야 한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_17069_파이프옮기기2 {
static int N;
static int[][] map;
static long[][][] dp;
static int cnt;

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

    map = new int[N][N];
    dp = new long[N][N][3];
    StringTokenizer st = null;
    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());
        }
    }

    dp[0][1][0] = 1;
    for (int i = 1; i < N; i++) {
        if (map[0][i] == 0) {
            dp[0][i][0] = 1;
        } else {
            break;
        }
    }

    for (int i = 1; i < N; i++) {
        for (int j = 2; j < N; j++) {
            if (map[i][j] == 1)
                continue;
            dp[i][j][0] = dp[i][j - 1][0] + dp[i][j - 1][2];
            dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j][2];
            if (map[i - 1][j] == 0 && map[i][j - 1] == 0)
                dp[i][j][2] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];

        }
    }

    long sum = 0;
    for (int i = 0; i < 3; i++) {
        sum += dp[N - 1][N - 1][i];
    }

    System.out.println(sum);

}

}