[백준] 17069번: 파이프 옮기기 2

문제

[백준] 17069번: 파이프 옮기기 2

분석

N x N 격자 판이 주어질 때 (1,1)과 (1,2)를 차지한 파이프를 옮겨서 한쪽 끝을 N, N으로 이동시키는 방법의 개수를 구하는 문제이다.
파이프를 옮기는 방법은 형태에 따라 아래의 사진과 같다.

이 문제는 상태에 따른 경우의 수를 누적해나가는 문제이기 때문에 dp를 떠올릴 수 있다.
상태는 파이프 타입과 위치로 나타내고 저장하는 값을 경우의 수로 나타낸다.
그러면 dp 테이블을 dp[타입][행][열] = 경우의 수; 로 정의할 수 있다. 여기서 위치는 파이프 끝부분(오른쪽 or 아래, 대각 아래)을 생각하면 된다.

경우를 나눠보면
일단 격자 값이 1인 경우는 벽이기 때문에 놓지 못하여 continue한다.
가로 일 때 똑같은 모양의 한 칸 왼쪽에서 온 경우와 대각 모양의 한 칸 왼쪽에서 온 경우를 더하면 된다.
세로 일 때는 똑같은 모양의 한 칸 위쪽에서 온 경우와 대각 모양의 한 칸 위쪽에서 온 경우를 더하면 된다.
대각 모양일 때는 가로 모양의 대각선 위쪽에서 온 경우와 세로 모양의 대각선 위쪽에서 온 경우와 똑같은 모양의 대각선 위쪽에서 온 경우를 더하면 된다. 다만 대각 모양일 경우는 주변 3칸이 모두 비어있어야 되기 때문에 grid[i][j-1]과 grid[i-1][j]가 1이 아니어야 가능하다.

대각 선택 없이 가로 세로 선택지만 있다고 가정해도 2^31 경우가 나온다. int에 경우를 저장하면 overflow가 나기 때문에 long타입에 저장해 준다.

시간 복잡도는 반복문 두 번으로 O(N^2)이 된다.

코드

해결언어 : Java

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

public class Main {
	static int N;
	static int[][] grid;
	static long[][][] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		grid = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				grid[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		dp = new long[3][N + 1][N + 1];
		dp[0][1][2] = 1; // type 0:가로, 위치 (1, 2)
		for (int i = 1; i <= N; i++) {
			for (int j = 3; j <= N; j++) {
				if (grid[i][j] == 1)
					continue;
				dp[0][i][j] = dp[0][i][j - 1] + dp[2][i][j - 1];
				dp[1][i][j] = dp[1][i - 1][j] + dp[2][i - 1][j];
				if (grid[i - 1][j] == 0 && grid[i][j - 1] == 0)
					dp[2][i][j] = dp[0][i - 1][j - 1] + dp[1][i - 1][j - 1] + dp[2][i - 1][j - 1];
			}
		}
		System.out.println(dp[0][N][N] + dp[1][N][N] + dp[2][N][N]);
		br.close();
	}

}