백준 17070번 - 파이프 옮기기 1

문제

백준 17070번 - 파이프 옮기기 1

아이디어

• dp[x][y][k]를 (x, y)에 k 방향으로 도착한 경우의 수라고 가정한다.
• k는 가로(0), 세로(1), 대각선(2)으로 나눌 수 있다.
• (x, y) 위치에 가로(0)로 도착하는 경우의 수는 이전 열에서 가로로 도착한 경우의 수와 이전 열에서 대각선으로 도착한 경우의 수를 합한 것과 같다.
• (x, y) 위치에 세로(1)로 도착하는 경우의 수는 이전 행에서 세로로 도착한 경우의 수와 이전 행에서 대각선으로 도착한 경우의 수를 합한 것과 같다.
• (x, y) 위치에 대각선(2)으로 도착하는 경우의 수는 대각선 왼쪽 위에서 가로, 세로, 대각선으로 도착하는 경우의 수의 합과 같다.
• 이때 대각선은 한번 더 생각해야 할 것이 도착하는 곳 외에 두 곳도 빈칸이어야 한다.
• 이런 점들을 유의하면서 경우의 수 배열을 채워나간다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N^2)

코드 구현

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

public class BJ_17070 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[][] home = new int[n + 1][n + 1];
        int[][][] dp = new int[n + 1][n + 1][3]; //0=가로, 1=세로, 2=대각선

        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                home[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[1][2][0] = 1; //초반 (1, 2)에는 가로로 도착한다.

        //1행은 가로로만 이동할 수밖에 없으므로 따로 먼저 처리한다.
        for (int i = 3; i <= n; i++) {
            if (home[1][i] == 0) {
                dp[1][i][0] = dp[1][i - 1][0];
            }
        }

        for (int x = 2; x <= n; x++) { //2행부터 n행
            for (int y = 1; y <= n; y++) { //1열부터 n열
                if (home[x][y] == 0) {

                    //(x, y) 위치에 가로로 도착하는 경우
                    dp[x][y][0] = dp[x][y - 1][0] + dp[x][y - 1][2];

                    //(x, y) 위치에 세로로 도착하는 경우
                    dp[x][y][1] = dp[x - 1][y][1] + dp[x - 1][y][2];

                    //(x, y) 위치에 대각선으로 도착하는 경우
                    if (home[x - 1][y] == 0 && home[x][y - 1] == 0) {
                        dp[x][y][2] = dp[x - 1][y - 1][0] + dp[x - 1][y - 1][1] + dp[x - 1][y - 1][2];
                    }
                }
            }
        }

        System.out.println(dp[n][n][0] + dp[n][n][1] + dp[n][n][2]);
    }
}