[백준 - 17069][GOLD 4][해설 X] - 파이프 옮기기 2 (JAVA)

문제 링크

---

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

 

문제

---

유현이가 새 집으로 이사했다. 새 집의 크기는 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을 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int WIDTH = 0;
    private static int HEIGHT = 1;
    private static int DIAG = 2;

    private static int WALL = 1;

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

        int N = Integer.parseInt(br.readLine());
        int[][] map = new int[N+1][N+1];

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

        long[][][]dp = new long[3][N+1][N+1];
        dp[WIDTH][1][2] =1; //좌표 (1 , 2) 경우의수 초기화

        //좌표 (1 , i) 초기화
        for(int i=3;i<=N;i++){
            //벽인경우 이후 좌표도 이동할 수 없다.
            if(map[1][i] == WALL){
                break;
            }
            dp[WIDTH][1][i] = 1;
        }
        
        //행 좌표가 2이상인 경우의 수 구하기
        for(int i=2;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(map[i][j] == WALL){
                    continue;
                }
                
                //가로로 움직인 경우
                dp[WIDTH][i][j] = dp[WIDTH][i][j-1] + dp[DIAG][i][j-1];
                //세로로 움직인 경우
                dp[HEIGHT][i][j] = dp[HEIGHT][i-1][j] + dp[DIAG][i-1][j];
                
                //대각선으로 움직인 경우
                //대각선으로 움직이려면 위칸과 왼쪽칸이 벽이 아니어야 가능하다
                if(map[i-1][j] != WALL && map[i][j-1] != WALL) {
                    dp[DIAG][i][j] = dp[DIAG][i-1][j-1] + dp[WIDTH][i-1][j-1] + dp[HEIGHT][i-1][j-1];
                }
            }
        }

        long count = dp[WIDTH][N][N] + dp[DIAG][N][N] + dp[HEIGHT][N][N];

        System.out.println(count);
    }
}

 

실행 결과

---

 

팁

---

• DP 문제는 항상 점화식을 먼저 생각해야 한다.
• 목표 모양을 위해 어떤 모양을 만들어야 하는지 생각하자
• int범위인지 확인하자