[백준 / BOJ 17069] 파이프 옮기기 2

https://www.acmicpc.net/problem/17069

17069번: 파이프 옮기기 2

문제

---

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

입력

---

첫째 줄에 집의 크기 N(3 ≤ N ≤ 32)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.

출력

---

첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다.

 

풀이

---

Dynamic Programming 알고리즘으로 풀었다. 

DP[i][j][k] ➡️ (i, j) 위치에 k 방향으로 파이프가 도착할 수 있는 방법의 수를 저장할 변수

k는 0 : 가로, 1 : 세로, 2 : 대각선 방향이다.

우선 가로와 세로를 보면

📌 가로는 가로방향에서, 대각선방향에서만 가능하고, 세로는 세로방향에서, 대각선방향에서만 가능하다. 

즉 DP[i][j][0]은 (i, j)에 가로로 도착하는 것을 의미하므로, (i-1, j)에서 이동한다. 여기서 최대 45도만 회전가능하므로 (i-1, j)에세로로 도착한 횟수는 더해주지않는다. 

점화식을 세우면‼️

• DP[i][j][0] = DP[i-1][j][0] + DP[i-1][j][2]
• DP[i][j][1] = DP[i][j-1][1] + DP[i][j-1][2]

📌 대각선은 가로, 세로, 대각선 모두 가능하다. 그러나 주의할 점 ‼️(i-1, j) & (i, j-1)이 벽이여서는 안된다.

점화식을 세우면 ‼️

• DP[i][j][0] = DP[i-1][j-1][0] + DP[i-1][j-1][1] + DP[i-1][j-1][2]

최종적인 답으로, DP[N][N][0] + DP[N][N][1] + DP[N][N][2] 이다.

코드

---

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

public class Main_BOJ_17069_파이프옮기기2 {
    
    static int[][] house;
    static long[][][] DP;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;
        
        int n = Integer.parseInt(br.readLine());
        house = new int[n+1][n+1];
        // 0 : 가로, 1 : 세로, 2 : 대각선
        DP = new long[n+1][n+1][3];

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

        DP[1][2][0] = 1;
        
        for(int i = 1; i <= n ; i++){
            for(int j = 3 ; j <= n ; j++){
                if(house[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(house[i-1][j] == 0 && house[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];
            }
        }

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