백준 17069번 - 파이프 옮기기 2

문제

백준 17069번 - 파이프 옮기기 2

아이디어

특정 좌표에 가로, 세로 또는 대각선으로 올 수 있다. 따라서 동적 프로그래밍으로 마지막 좌표에 가로, 세로, 대각선으로 오는 경우의 수의 합을 구한다.

코드 구현 - 자바

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

public class BJ_17069 {

    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][n];
        long[][][] dp = new long[n][n][3]; //0=가로, 1=세로, 2=대각선
        dp[0][1][0] = 1;

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

        //0행
        for (int i = 2; i < n; i++) {
            if (home[0][i] == 0) {
                dp[0][i][0] = dp[0][i - 1][0];
            }
        }

        //1행 ~ N-1행
        for (int i = 1; i < n; i++) {
            //2열 ~ N-1열
            for (int j = 2; j < n; j++) {
                if (home[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][2] + dp[i - 1][j][1]; //세로 도칙

                //대각선 도착
                if (home[i][j - 1] == 0 && home[i - 1][j] == 0) {
                    dp[i][j][2] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];
                }
            }
        }

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

• 특정 위치에 가로로 도착했다는 것은 가로에서 가로 오거나, 대각선에서 가로로 오는 경우 밖에 없다. 따라서 이전 가로의 가로로 도착한 경우 + 대각선으로 도착한 경우이다.
• 특정 위치에 세로로 도착했다는 것은 세로에서 세로로 오거나, 대각선에서 세로로 오는 경우 밖에 없다. 따라서 이전 세로의 세로로 도착한 경우 + 대각선으로 도착한 경우이다.
• 특정 위치의 대각선으로 도착했다는 것은 가로에서 대각선, 세로에서 대각선, 대각선에서 대각선 모두 가능하다. 따라서 이전 대각선의 세 가지 도착한 경우이다. 다만 대각선은 도착지 외에 두 곳도 빈 칸이어야 하므로 추가적인 검증이 필요하다.
• 문제 조건상 0행과 1열은 절대 도착할 수 없기 때문에 2열부터 값을 채웠다.

예상 시간 복잡도

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